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

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)
``````

``````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
``````

Θ(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!