Orders of Growth: Difficult Solutions

Finding orders of growth 

def f1(n):
    if n == 0:
        return 0
    while n > 0:
        print(n)
        n - = 1
    return f1(n // 2)
Θ(n) - For each call to f1, the while loop is run n times (n work is completed), so the total amount of work is n + n/2 + n/4... + 1 which simplifies to n work.

def f2(n):
    if n == 0:
        return 0
    while n > 0:
        print(n)
        n *= 2
    return f2(n // 2) + f2(n // 2)
Θ(nlogn) - For each call, there is logn work completed. You can draw out a tree where each node is one call to f2, and see that you have logn + 2logn + 4logn + ... + nlogn, which simplifies to nlogn.

def f3(n):
    for x in range(n):
        if x % n == 0:
            return f3(n - 1)
Θ(n2) - For each call, there is n work done, and the only time that f3(n - 1) is called is when x reaches n, so the total amount of work is n + (n - 1) + (n - 2) + ... + 1, which simplifies to n2 work.

def f4(n, m):
    if n == 0:
        return 0
    for x in range(m):
        f4(n - 1, m)
    return 1
Θ(mn) - You can view this as a more general case of 2n, draw out the tree to help.