What is the Big O of this while loop?-CodePudding

Normally when I see a loop, I assume it is O(n). But this was given as an interview question and seems to easy.

let a = 1;

while(a < n){
  a = a * 2;
}

Am I oversimplifying? It appears to simply compute the powers of 2.

CodePudding user response：

Looks like a grows exponentially with n, so the loop will likely complete in O(log(n))

I haven't done all the math, but a is not LINEAR wrt n...

But if you put in a loop counter, that counter would approximate log-base-2(n)

CodePudding user response：

Never assume that a loop is always O(n). Loops that iterate over every element of a sequential container (like arrays) normally have a time complexity of O(n), but it ultimately depends on the the condition of the loop and how the loop iterates. In your case, a is doubling in value until it becomes greater than or equal to n. If you double n a few times this is what you see:

n   # iterations
----------------
1        0
2        1
4        2
8        3
16       4
32       5
64       6

As you can see, the number of iterations is proportional to log(n), making the time complexity O(log n).