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.