Orders of Growth: basic-level questions

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

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

Conceptual Questions

Question 1

What is the time complexity of this function in big-Theta (θ) notation?

def one(n):
    for a in range(n):
        for b in range(n/2):
            for c in range(n/4):
                print(a + b + c)

θ(n3)

Question 2

What is the time complexity of this function in big-Theta (θ) notation?

def two(n):
    for a in range(n):
        for b in range(1000000000):
            for c in range(n):
                print(a + b + c)

θ(n2)

Question 3

What is the time complexity of this function in big-Theta (θ) notation?

def three(n):
    while n > 1:
        result = n * n
        print(result)
        n = n / 10
    return False

θ(logn)

Question 4

What is the time complexity of this function in big-Theta (θ) notation?

def four(lst):
    if len(lst) < 12345:
        return lst[0]
    return four(lst[1:])

θ(n), where n is the length of the list.

Question 5

What is the time complexity of this function in big-Theta (θ) notation?

def five(n):
    def helper(x):
        return x + n
    return helper(n/2)

θ(1)

Question 6

What is the time complexity of this function in big-Theta (θ) notation?

def reverse(lst):
    if not lst:
        return []
    result = reverse(lst[1:])
    result.append(lst[0])
    return result

θ(n), where n is the size of the list.