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

Question

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.

Answer 1

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.