## Orders of Growth: Conceptual **Solutions**

### simplifying big theta

Simplify the following functions to their big theta equivalent.

3n^{3} + 2n^{2} + n

**Θ(n ^{3})**

4*n*logn + 100logn

**Θ(nlogn)**

100000n + n!

**Θ(n!)**

12345678

**Θ(1)**

n! + n^{n}

**Θ(n ^{n})**

### FINDING ORDERS OF GROWTH

For all of the following functions, find their order of growth as a function of n and write it in big theta notation.

def f1(n):

while n > 0:

print(“I love computer science”)

n=n-1

return n

**Θ(n) - n iterations of the while loop**

def f2(n):

while n > 0:

print(“I love 61A”)

n = n * 2

return n

**Θ(logn) - Instead of n iterations of the while loop, there are logn because each iteration, n gets multiplied by 2, rather than incremented by 1**

def f3(n):

m = 100000

while m > 0:

n=n+1

m=m-1

return n

**Θ(1) - The while loop is based off of m and m is always 100000**

def f4(n):

if n <= 0:

return 0

else:

return f4(n - 1) + f4(n - 1)

**Θ(2 ^{n}) - You can draw out a tree of recursive calls where each node splits into two new ones. The tree has height n, so you have 2^{n} + (2^{n} - 1) + .... + 1 runs of the function, which gives 2^{n}**