0

What should be the time complexity for below code block and why:

int a = 0; 
for (i = 0; i < N; i++) { 
 for (j = N; j > i; j--) { 
    a = a + i + j; 
 } 
}

Outer loop: O(N)

Inner loop: Go on decreasing by the rate of i,

Dry run: Suppose n=10 as

When i=0, then j runs from j: 10 -> 1, i.e. 10 times or n times

When i=1, then j runs from j: 10 -> 2, i.e. 9 times or n-1 times

When i=2, then j runs from j: 10 -> 3, i.e. 8 times or n-2 times

--

When i=8, then j runs from j: 10 -> 9, i.e. 2 times

When i=9, then j runs from j: 10 -> 10, i.e. 1 times

So the inner loop comes out to be: n+ (n-1) + (n-2) . . . . (2) + (1)

So, it would be 1 + 2 + 3 ... (n-1) + (n)= n*(n+1)/2 = O(n*n)

Time Complexity: O(n*n*n)

Is this correct or not?

Heretic Monkey
  • 11,687
  • 7
  • 53
  • 122
Kumar Ashutosh
  • 1,121
  • 10
  • 33
  • 1
    You're actually doubly-counting a lot of the work you need to do. You're correct that the inner loop will run n + (n-1) + (n-2) + ... + 1 times, which is O(n2) times, but you're already summing up across all iterations of the outer loop. You don't need to multiply that value by O(n) one more time. The most accurate answer would be O(n2). – MMG Mar 31 '20 at 19:05
  • 1
    See here: https://stackoverflow.com/questions/11094330/determining-the-big-o-runtimes-of-these-different-loops – MMG Mar 31 '20 at 19:06
  • Does this answer your question? [Determining the big-O runtimes of these different loops?](https://stackoverflow.com/questions/11094330/determining-the-big-o-runtimes-of-these-different-loops) – MMG Apr 01 '20 at 02:03

2 Answers2

3

You have one n to much in the product.

When summing up n+ (n-1) + (n-2) . . . . (2) + (1) you already simulate the effect of the outer loop and therefor you don't have to multiply by n afterwards.

And therefor the result becomes O(n²).

QuantumDeveloper
  • 737
  • 6
  • 15
  • So , is it not that, For every 1 time of outer-loop, inner-loop will execute n^2 time ? How is this(outer loop run time) included in inner-loop runtime? – Kumar Ashutosh Mar 31 '20 at 18:49
  • 1
    The outer loop is included because you sum up the runtime of the inner loop for every repetition of the outer loop, so you essentially end up with the calculation of both loops. If that's not clear to you, here is another way to look at it: The inner loop takes on average `n/2` repetitions, so the inner loop takes `O(n)` and combined with the outer loop that's `O(n²)` – QuantumDeveloper Mar 31 '20 at 19:04
1

The way you are calculating is wrong. The outer loop runs in O(N) and so too the nested inner loop.

So the above code becomes (O(N^2)).

Pritam Banerjee
  • 17,953
  • 10
  • 93
  • 108