Orders of Growth: exam-level questions

If you need help reviewing Orders of Growth, take a look at these resources:

This link (from the Summer 2012 version of 61A) has some practice problems for orders of growth. Take a look!

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

Conceptual Questions

Question 1

Find the time complexity of main in big-Theta (θ) notation.

def helper(x):
    for i in range(x):
        print(i)
    return x

def main(n):
    if n == 2:
        return 0
    else:
        return helper(n - 1) + helper(n - 2)

θ(n)

Question 2

Find the time complexity of bar in big-Theta (θ) notation.

def foo(x):
    for i in range(x):
        for j in range(x):
            print(x)

def bar(n):
    while n > 0:
        foo(100000)
        n -= 1

θ(n)

Question 3

Find the time complexity of funny in big-Theta (θ) notation.

def joke(n):
    for i in range(n**2):
        print(i)

def funny(n):
    for i in range(n**2):
        print(joke(100))
    return 'haha'

θ(n2)