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.

CodePudding user response：

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