Big O - Nested loops

Question

void bar(int N){
  int c=0;
  for (int i=0; i<N*N; i++)
    for (int j= i; j< N; j++)
      c++;
}

The outer (and inner) loops above never get past N. Would this mean the Big O is N*N (N for the outer and N/2 for the inner)?

Answer 1

If you do this

for (int i = 0; i < N; i++)
  for (int j = i; j < N; j++)
    …

you will iterate N times in the inner loop first, then N-1, then N-2, etc., which sums to N(N-1)/2. This loop runs in O(N²), that is the square of the outer loop.

In your case, your code is equivalent to

for (int i = 0; i < N; i++)
  for (int j = i; j < N; j++)
    c++;

since for every positive integer we have N² ≥ N and the compiler should be clever enough to notice that it makes no sense to continue running the outer loop if i is greater than N. So the complexity is indeed O(N²).

If you print N and c after your program runs, you will notice that when N gets doubled, c is almost multiplied by 4 (2²):

N = 1, c = 1
N = 2, c = 3
N = 4, c = 10
N = 8, c = 36
N = 16, c = 136
N = 32, c = 528
N = 64, c = 2080
N = 128, c = 8256
N = 256, c = 32896
N = 512, c = 131328
N = 1024, c = 524800
N = 2048, c = 2098176