Why is this function/loop O(log n) and not O(n)?

问题:

This function is O(log(n)). Why? Isn't it looping up to n?

function fxn($n) {
    for ($i = 1; $i <= $n; $i *= 2)
        echo $i;
}

I'm pretty new to O(n) analysis by the way. This function sure looks O(n) though since it loops up to n.

回答1:

This loop would be O(n):

function fxn($n) {
    for ($i = 0; $i <= $n; $i++)
        echo $i;
}

Because$i takes on the values:

1, 2, 3, 4, 5, 6, 7, ..., n

But this loop is only O(log(n)):

function fxn($n) {
    for ($i = 1; $i <= $n; $i *= 2)
        echo $i;
}

Because $i takes on the values:

1, 2, 4, 8, 16, 32, 64, ..., n

And a sequence that grows in that manner is called "logarithmic".

回答2:

It's not looping through all of the elements, in each step it jumps over twice of the elements of the previous step - because of the $i *= 2 part. That is, assuming that $i starts in a value greater than zero, otherwise it's an infinite loop: $i will always be 0 as it is written.

回答3:

Your code loops up to n but not by ones (or any constant value) which would make it O(n).

This is what it does:

       1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
       |  |     |           |                       |
       +--+-----+-----------+-----------------------+
Steps    1    2        3               4

Because it's doubling each time, it's actually O(log N), similar to the way a binary tree search halves the search space on each iteration.

回答4:

Note: that your function will never end because you're starting at 0, and 0 * 2 = 0. I'll assume your loop starts at 1.

The loop increments by a multiple of 2 every time, which is why the runtime is O(lg(n)).

Let's consider a simple example where n = 128.

here are the values of i for each iteration: 1, 2, 4, 8, 16, 32, 64, 128. Thus, you've gone through 8 values.

lg(128) = 7 (lg = log in base 2)
        = 8 - 1

Note here that the - 1 is a constant, so it doesn't affect our runtime calculation.

If the loop incremented by 1 (or any constant, k) the runtime would be O(n). The important thing to consider here is the difference between a geometric series and an arithmetic series, which gives you different runtimes.