Time complexity of an unorthodox nested for loop

Question

I have read through few posts dealing with time complexity and loops and have a question regarding the time complexity of the following nested for loop, in order to reassure my solution:

for(int i = 0; i < n; i++){
 for(int j = n; j > i; j--){
      #print something
 }}

Now I know that the time complexity of the outer loop is O(n), as the number of iterations are n. I guess the inner loop, however, should only iterate n/2 times, as while i is counting up towards n, j is decreasing towards 0 from n in the same manner. Thus, the inner loop should stop after n/2 iterations. Therefore, I would suggest that the time complexity is O(n*n/2) or simplified O(n^2). Am I right? Thanks in advance.

Why is it "unorthodox"? And, although the average number of times the inner loop runs is N/2, it varies because i is changing. — meowgoesthedog
– meowgoesthedog, Commented Apr 20, 2018 at 12:05

Abhishek Keshri · Accepted Answer · 2018-04-20 18:54:08Z

2

Let us see how the loop is running:

i=0 => j will run from 1 to n => n times
i=1 => j will run from 2 to n => (n-1) times
i=2 => j will run from 3 to n => (n-2) times
............................................
i=n-1 => j will run from n to n => 1 time

So adding all the terms, we get

n + (n-1) + (n-2) + .... + 1 = n*(n+1)/2

This equals O(n^2). So yes your conclusion was correct.

answered Apr 20, 2018 at 18:54

Abhishek Keshri

3,31417 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Time complexity of an unorthodox nested for loop

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related