The number of times you can double a starting value of 1 to get n or more is the same as the number of times you can halve a starting value of n before you get a value less than 1. Either way, the number of steps is log2(n).

So the outer loop runs O(log n) times and each instance of the inner loop runs O(log n) times. The total time is O(log n)^2 = O((log n)^2) = O(log^2 n).

14,978,669 members