Search code examples
pythonmaster-theorem

What is the running time of these functions?

What is the running time? 

def a(n):
    if n % 2 == 0:
        return n
    else:
        return a(n/2)

My guess T(n) = T(n/2) + 1, then use master theorem.

How about this function:

def b(n):
    for i in range(n):
        print(a(i))

This is my guess.

T(n) = nT(n/2) + 1

Solution

  • First one is O(logN) second one is O(NlogN).

    1) You're cutting the problem in half every iteration. So the total number of times you iterate is:

    i such that 2**i = N, in math i = logN in base 2. There for O(logN)

    2) You're iterating through the entire list of size N so O(N) but you are calling a logN function on every iteration. So we are calling a logN function N times. This is O(NlogN).