Big-O Nested While Loop

Question

i <-- 1
while(i < n)
   j <--1
   while(j < i)
      j <-- j * 2
   i <-- i + 1
done

My shot at this would be O(log n) for the inner loop. And I'm guessing the outer loop is O(n), for an overall complexity of O(n log n). Confirm?

Answer 1

You may proceed formally, step by step, using Sigma notation to obtain the exact number of iterations - Look at Discrete Loops and Worst Case Performance paper (page 10).

The result has been empirically verified.