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.