Search code examples
pythonfunctionbig-ocomplexity-theory

Understanding time complexity, big-O notation


Edit- this question is from a former test in my course, the official answer is O(n)

I need help understanding why does the run-time complexity in the following code is O(n) and not O(n*log(n))

def fun(n):
   total = 0
   while n > 5:
       n = n // 2
       total += sum(range(n))
   return total

The while loop executes log(n) times, and in each iteration the sum function sums n/2 numbers, therefore it's complexity is o(n), I see that each while iteration there's less numbers to sum, but i don't understand why it's O(n).

Thank you.


Solution

  • So I've figured it out.

    Each while iteration sums n/2 items. which means total iterations are n\2 + n\4 +n\8 +..., and this sum converges to n