What is the running time of the algorithm

9 次查看(过去 30 天)
I have this code:
n = length(V);
S = zeros(n,2*n);
for i = 1:n
for j = 2:i
for k = 1:n
S(i,j+k) = V(i);
end
end
end
i am trying to find the theoretical complexity. This is what i did thus far
Line 1: 1
Line 2: 1
Line 3 : n
Line 4 : (n(n-1))/2
Line 5 : n
Line 6 : n
So my question is: Am i supposed to multiply the running times of Line 5 and 6 by the running time of each of the two outer 'for loops'
Thank You

回答(1 个)

Akshat
Akshat 2024-11-6,11:25
In the code that you have shared, the running times of each of the loops will get multiplied to each other.
We can visualise it something like this:
The loop iterating "k" will run "n" times for every iteration of "j". The loop iterating over "j" will run "i-1" times, as it runs from 2 to "i". Now, as "i" varies, we can see the loop iterating over "i" will run (n-1)*n. "i" itself has n iterations, so all the loops will run n*(n*(n-1)) ~ n^3.
The only thing I would like to point out that the line 2, will have a O(n^2) complexity, as allocation of space to a 2D matrix takes up time.
The overall complexity of the code will still be O(n^3).
Hope this helps.

类别

Help CenterFile Exchange 中查找有关 Fourier Analysis and Filtering 的更多信息

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by