Time Complexity of a weird loop

Question

What's the time complexity of this loop?

for(int i = 0; i < n*n; i *= 2)

   { //Something with O(1) complexity here }

I would guess O(log n*n).

Answer 1

You are right, as i doubles on each iteration and the loop terminates when i >= n², making it run for O(log n²) iterations.

However, notice that O(log n²) = O(2 log n) = O(log n).

EDIT: However, as Zilog80 points out, this piece of code initializes i as 0, which will cause the loop to run for infinity since 0 * 2 = 0. If you initialize it as some positive (constant) number, however, then your calculation is correct.