Orders of Growth: Conceptual
Simplifying Big Theta
Simplify the following functions to their big theta equivalent.
3n3 + 2n2 + n
4nlogn + 100logn
100000n + n!
12345678
n! + 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
def f2(n):
while n > 0:
print(“I love 61A”)
n=n*2
return n
def f3(n):
m = 100000
while m > 0:
n=n+1
m=m-1
return n
def f4(n):
if n <= 0:
return 0
else:
return f4(n - 1) + f4(n - 1)