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