Big-O value for iteration sof a while loop

问题:

Give a big-O estimate for the following program

i=1
while ( i <= n ) {
    i = 2*i
}

by drawing a quick table, comparing the value of i to each iteration we see that:

if n=5 we need 6 iterations

if n=7 we need 8 iterations, and so on...

So I say:

how many iterations do we need until 2^k > n (where k is the number of iterations)

 2^k > n
 log(2^k) > log(n)
 k > log(n)

where log is of base 2.

But I am stuck now... how do I get the big-O from this?

回答1:

Well, you have the answer alraedy. The k tells you how many iterations you need at most. When you take an n, with log(n) iterations you will end the loop. Thus, the asymptotic running time of the algorithm is O(log n). The base of the logarithm doesn't matter, because it is just a constant factor: e.g. ln n = log(n)/log(e). You won't see this factor (log e in this case) under Big-O anyway.