Q:

Big O of empty loops

If I have a loop construction like this
for(int i=1; i<n;i++)
   for(int j=1; j<n;j++);

O(n2) or O(0)?
Assume that inside the loop is an if:
for(int i=1; i<n;i++)
   for(int j=1; j<n;j++)
      if(a==b) do();

and I want to know best and worst case, assuming do() is O(1).
Worst: O(n2) if statement always true
Best: O(0) if statement always false
Is that correct?

A:

There's no such thing as O(0), in our context; it'd be effectively constant-time (O(1)), if optimized away.
As for whether that's the case, no.  As written, it's still O(N^number of nested loops).  An optimizer might remove the code entirely, but the "worst case" is that it doesn't, and the CPU's spinning its wheels. through those loops.

A:

Take n = 3, for the first loop, the following happens:
i = 1
i < 3 => true
  j = 1
  j < 3 => true
  j++
  j < 3 => true
  j++
  j < 3 => false
i++
i < 3 => true
  j = 1
...

All these increments and checks still need to happen regardless of whether or not there's any other code in the loop.
So it will be best + worst case O(n2).
There is of course the possibility that the optimiser will see nothing happens in the loop and removes it completely. But saying the best-case for loop is O(1) will probably be considered wrong, even though it's technically correct.

