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

Why does this code has time complexity of O(NN) ? Are all nested loops with n,m,q,.... bounds have a complexity of O(nm*q....) even though few iterations of the loops will not happen?

DragneelFPS
  • 453
  • 4
  • 12
  • 1
    Related: https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm, https://stackoverflow.com/questions/33858889/why-is-the-big-o-complexity-of-this-algorithm-on – Cody Gray - on strike Jun 17 '17 at 14:47
  • https://stackoverflow.com/questions/44085863/what-is-the-time-complexity-of-the-following-algorithm/44086434#44086434 – Matt Timmermans Jun 17 '17 at 16:27

2 Answers2

1

The reason for this is that constant factors are ignored in Big-O notation.

Your outer loop runs N times, while the inner loop runs on average N/2 times for each of the outer iterations.

This gives O(N * 1/2 * N) executions of the statements within the inner loop. Since we ignore constant factors, we end up with O(N * N) which is O(N^2).

The reason for omitting constants is simple: Big-O notation is about what happens when N is big. If you look at it this way - O((N^2)/2) - you see that increasing N has much more influence in the term, than whether or not we omit the division by two.

thertweck
  • 1,120
  • 8
  • 24
1

I wouldn't say all nested loops have that complexity, but this one certainly does. The number of iterations through the inner loop is something like this (there might be an off-by-one error):

  • i = 0: N times
  • i = 1: N - 1 times
  • i = 2: N - 2 times
  • . . .
  • i = N-1: 1 times
  • i = N: 0 times

Let's count the total number of times the innermost code is called. In this case, you can figure this out arithmetically. The innermost code is executed about N * (N + 1) / 2 times (this is the sum of elements from 1 to N). This simplifies to 0.5 * N^2 + 0.5 * N and that has a complexity of N^2.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Gordon Linoff
  • 1,242,037
  • 58
  • 646
  • 786