0

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
xlax
  • 2,661
  • 6
  • 12
  • 15

1 Answers1

0

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

  • `2n-1` is the total number of operations performed by the inner loop, not the nubmer of operations performed on every iteration of the outer loop. Therefore, `2n-1` and `log(n)` should be added, not multiplied; and the total time complexity will be `O(n)`. See also: http://stackoverflow.com/questions/41708311/two-loops-but-thetan – Anton Jan 29 '17 at 21:47