algorithm - Worst case complexity for this python code -

what worst case time complexity of following:

def fun(n):     count=0     i=n     while i>0:         j in range(0,i):             count+=1         i/=2     return count

worst case time complexity if n big integer.

o(log(n)*n) (guessing).

here's how came conclusion.

while i>0:         ...         i/=2

this run log(n) times because it's getting halved every time runs.

for j in range(0,i):

this run n times first, n/2 times 2nd time, , on. so, total running time line n + n/2 + n/4 .... 1 = (2n-1)

count+=1

this cheap operation o(1).

thus making total running time of function o(log(n)) * o(2n-1), if n integer. simplifying becomes o(log(n)*(n)).

WIKI