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
0 个评论
回答(1 个)
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.
0 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Fourier Analysis and Filtering 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!