What is the worst case time complexity of the following:
def fun(n):
count=0
i=n
while i>0:
for j in range(0,i):
count+=1
i/=2
return count
What is the worst case time complexity of the following:
def fun(n):
count=0
i=n
while i>0:
for j in range(0,i):
count+=1
i/=2
return count
Worst case time complexity if n is really big integer.
O(log(n)*n) (Guessing).
Here's how I came to my conclusion.
while i>0:
...
i/=2
This will run log(n) times because it's getting halved every time it runs.
for j in range(0,i):
This will run n times first, n/2 times the 2nd time, and so on. So, total running time for this line is n + n/2 + n/4 .... 1 = (2n-1)
count+=1
This is a cheap operation so is O(1).
Thus making total running time of this function O(log(n)) * O(2n-1), if n is an integer. Simplifying becomes O(log(n)*(n)).