O(n) vs O(nlogn) Time Complexity

Question

I came across this time complexity example online, and am slightly confused.

x = n
while ( x > 0 ) {
    y = x
    while ( y > 0 ) {
        y = y - 1
    }
    x = x / 2
 }

The answer is stated as O(n). I am wondering why it is not O(nlogn). The reason why I say this is because the outer loop looks to be logarithmic, while the inner loop appears to be linear. If y=n (instead of x), would the time complexity THEN be O(nlogn)? If so, why?

Answer 1

How many time does it pass on y=y-1? That will measure the complexity, right?

• When x=n, it passes n times.
• When x=n/2, it passes n/2 times.
• When x=n/4, it passes n/4 times.
• ...

So it passes n + n/2 + n/4... which sum up to 2n.

Thus total complexity is O(n).

Don't be fooled, inner loop is linear but not independently from the outer loop.

Answer 2

The inner loop is indeed linear, but each iteration does not take n steps, but x steps for the current value of x which is iteratively halved, which means that a finer analysis is possible. You have over-estimated the cost of the inner loop. Consequently, the bound

O(n log n)

is also correct, but

O(n)

is a smaller bound. The smaller bound can be seen by reasoning that the i-th iteration of the inner loop takes

n / 2^i

steps; the runtime bound of O(n) follows from the fact that the sum of denominators is the geometric series, which converges to the constant 2.