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

**Θ(n ^{2}) - 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 n^{2} work.**

def f4(n, m):

if n == 0:

return 0

for x in range(m):

f4(n - 1, m)

return 1

**Θ(m ^{n}) - You can view this as a more general case of 2^{n}, draw out the tree to help.**