Compute time complexity of code

Question

Can someone help me on how to analyze the run-time of the given below pseudocode

for i = 1 to n
     k[i] = 0

for i = 1 to n
   for j = i to n
           k[i] = k[i] +j

I guess that it's time complexity is O(n^2). Please correct me if I am wrong.

Not a clear question, you can't ask others to analyse your code. This place is to ask good technical questions which after research have been found not solved. — SACn, Sep 24 '17 at 17:03

score 0 · Answer 1 · answered Sep 24 '17 at 17:10

The for loop consists of three elements. The assignment 1. The conditional branch. And the increment operation. If you can quantify the execution time for each line, you can calculate the overall time to execute. So for example call k[i] = 0 operation a. k[i] = k[i] +j. Operation b. The for loop assignment operation c. The for loop increment and conditional branch operation d.

This would yield: (sum(n - i) for i = 1 to n)*(b + d) + (2 + n)c + na.

Which I think would simplify to ~(b + d)*(n^2)/2 for very large values of n. So I would agree it's complexity is O(n^2).

score 0 · Answer 2 · answered Sep 24 '17 at 17:11

The way to analyze complexity of these nested loops is from the deepest loop.

for i = 1 to n
 k[i] = 0

for i = 1 to n
   for j = i to n
       k[i] = k[i] +j

For the first loop it is very easy to see the operation k[i] = 0 will be performed n times

So order of that is O(N)

Now for the nested loop, loop for j starts from i , where i loops from 1 to n and continues till n.

So the key question to ask how many times the loop is executing.

when i = 1 it will be executing N times when i = 2 it will be executing N-1 times ... when i = 1 it will be executing 1 time

so if you sum them all it becomes N + N-1+ ... 1 = N(N-1)/2 = N^2/2 - N/2

So the order of the nested loop is O(N^2/2)- O(N/2) = O(N^2)

Also for the 1st loop the order is O(N)

so the total time complexity id O(N) + O(N^2) = O(N^2)

Compute time complexity of code

2 Answers2