Orders of Growth: Conceptual Solutions

simplifying big theta

Simplify the following functions to their big theta equivalent.

3n3 + 2n2 + n
Θ(n3)

4nlogn + 100logn
Θ(nlogn)

100000n + n!
Θ(n!)

12345678
Θ(1)

n! + nn
Θ(nn)

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)
Θ(2n) - 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 2n + (2n - 1) + .... + 1 runs of the function, which gives 2n