Given the functions below, analyze the run time of each in Big Theta notation.

def factorial(n):
    if n < 2:
        return 1
    return n * factorial(n - 1)

def fib(n):
    if n < 2:
        return 1
    return fib(n - 1) + fib(n - 2)

def foo(n):
    while n > 1:
        print(n)
        n = n // 2

def bar(n):
    while n > 1:
        x = n
        while x > 1:
            print(n, x)
            x -= 1
        n -= 1

def baz(n):
    while n > 1:
        x = n
        while x > 1:
            print(n, x)
            x = x // 2
        n -= 1

def buffalo(n):
    while n > 0:
        if n % 7 == 0:
            return n
        n -= 1

def tricycle(n):
    sum = 0
    for i in range(n):
        for j in range(n):
          sum += j
    return sum

def yoyo(n):
    total, counter = 0, 0
    for i in range(n):
        while counter == 0:
            total += (i + counter)
            counter += 1
        return total

def toilet(n):
    i = n
    def boss(n):
        nonlocal i
        print(n)
        if i > 0:
            i -= 1
            boss(i)
        return i
    return boss(n // 2)

Toggle Solution

def factorial(n):
    if n < 2:
        return 1
    return n * factorial(n - 1)

Θ(n)

def fib(n):
    if n < 2:
        return 1
    return fib(n - 1) + fib(n - 2)

For the sake of this class, this is exponential and approximately Θ(2n). It is not exactly Θ(2n) and you will learn more about this in CS61B.

def foo(n):
    while n > 1:
        print(n)
        n = n // 2

Θ(log n)

def bar(n):
    while n > 1:
        x = n
        while x > 1:
            print(n, x)
            x -= 1
        n -= 1

Θ(n2)

def baz(n):
    while n > 1:
        x = n
        while x > 1:
            print(n, x)
            x = x // 2
        n -= 1

Θ(n log n)

def buffalo(n):
    while n > 0:
        if n % 7 == 0:
            return n
        n -= 1

Θ(1)

def tricycle(n):
    sum = 0
    for i in range(n):
        for j in range(n):
          sum += j
    return sum

Θ(n2)

def yoyo(n):
    total, counter = 0, 0
    for i in range(n):
        while counter == 0:
            total += (i + counter)
            counter += 1
        return total

Θ(1)

def toilet(n):
    i = n
    def boss(n):
        nonlocal i
        print(n)
        if i > 0:
            i -= 1
            boss(i)
        return i
    return boss(n // 2)

Θ(n)

I don't claim to be perfect so if you find an error on this page, please send me an email preferably with a link to this page so that I know what I need to fix!

comments powered by Disqus