- A+

Category：Languages

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?

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.