What is the running time of the algorithm

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

Answer 1

[Akshat]

Hi @Asemahle Ndamase,

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.