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)