Computing Iterative Time Complexity

#1

I have a doubt consider the case where,
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<"Hi";
}
}

In the above case, we can simply say that the time complexity of our program is O(N^2) , since the inner loop is running n times for each value of i hence the total time complexity will be O(N^2).

Now consider the case where,
for(int i=N;i>0;i=i/2;){
for(int j=0;j<i;j++){
// Something
}
}

Here in the above segment of the code, how do we compute the time complexity? If we do the traditional method. It would come out to be O(NLogN) as the outer loop will run O(LogN) times and for each value of i the inner loop will run O(N) times but which isn’t the actual answer.

Thanks.

#2

@raghav6 The inner loop does n iterations, then n/2, then n/4, etc.
So the total number of inner loop iterations is:

n + n/2 + n/4 + n/8 + … + 1 <= n * (1 + 1/2 + 1/4 + 1/8 + …)
= 2n
So Complexity is O(n).

Hope this helps :slightly_smiling_face:

#3

@pratyush63 okay? so our inner loop does depends on the outer loop and hence the time complexity will be computed like you’ve computed. But in the Case 1, where the inner loop is independent of the outer loop, the outer loop will also be considered?
I am getting confused in the case, when to consider only the inner loop to compute the time complexity and when not to. :sweat_smile::sweat_smile:

#4

@raghav6 Yes for Case 1 where inner loop is independent of outer loop, the inner loop will always run from 0 to < n for each value of i. So for each i, n computations are done for the inner loop. Then in total for i<n n^2 computations are being done. So the complexity is O(n^2).
You need to consider all the loops to find the complexity. When a loop depends on other loop, you need to check it properly as in Case 2. When all the loops are independent then you get the overall complexity by multiplying the complexity of each loop. In case 1, first loop independently is of O(n) and 2nd loop is also O(n). Overall complexity is O(n * n)=O(n^2)

1 Like
#5

Thank you @pratyush63 :smiley::smiley:
Resolved the doubt, also rated you 5 :star:

1 Like
#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like