Why Time Complexity is O(n) , not O(nlogn)

  • 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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: