Introduction
This topic material is based on Professor Mike Gelbart Algorithms and Data Structures course. It was adapted for our purposes.
import numpy as np
import matplotlib.pyplot as plt
import urllib.request
from collections import defaultdict, Counter
Exercise: Time Complexity¶
For each of the following functions, determine the time complexity as a function of the input $n$ using big-O notation and briefly justify your answer. If you get stuck, it's fair game to test things empirically and then try to understand what you observe. Please state your assumptions if you don’t know how long some operation in Python takes.
The first question is done for you, as an example.
def example(n):
for i in range(n):
print(i)
print(i**2)
x = 9
y = 10
example(5)
Sample Answer: The time complexity of example is $O(n)$ because the function loops over $n$ elements and only performs constant-time operations inside the loop.
Details:
- The function contains a
forloop that runsntimes. - Within this loop, two operations occur:
print(i)which is a constant-time operation, (O(1)).print(i**2)which is also a constant-time operation, (O(1)), as the squaring of a number is a simple arithmetic operation that doesn't depend on the size ofn.
The two operations inside the loop do not alter the overall number of iterations and are independent of each other, hence, they do not multiply the complexity.
- After the loop, there are two assignments:
x = 9andy = 10. Both are constant-time operations, (O(1)), and do not depend on the size of the inputn.
Since all operations inside the loop are (O(1)) and the loop runs n times, the total time complexity of the function is determined by the loop.
Therefore, the time complexity of the function example(n) is linear, (O(n)), where n is the size of the input. The two constant-time assignments outside the loop do not change the overall complexity because constant factors and lower-order terms are not considered in big-O notation.
def loopy(n):
for i in range(n):
for j in range(n):
print('i =', i, ' j =', j)
loopy(4)
Answer:
def triangle(n):
for i in range(n):
for j in range(i):
print("+", end='')
print("")
triangle(7)
Answer:
def foo(n):
x = np.zeros(n)
x = x + 1000
return x
print('size of x: ', len(foo(100000)))
Answer:
def bar(n):
x = np.zeros(1000)
x = x + n
return x
print('size of x: ', len(bar(100000)))
Answer:
def broken(n):
for i in range(n**2):
if i == n:
break # "break" exits the innermost loop
print(i)
broken(4)
Answer:
def cabin(n):
i = n
while i > 1:
print('i = ', i)
i = i // 2
Note: the // operator performs integer division, meaning the result is rounded down to the nearest integer.
cabin(2048)
Answer:
def cabin10(n):
i = n
while i > 1:
print('i = ', i)
i = i // 10
cabin10(2048)
Answer:
¶
For this question, answer in terms of both $m$ and $n$.
def blahblah(n, m):
x = 0
for i in range(n):
for j in range(m):
x = x + 1
for i in range(n):
x = x + 1
for i in range(m):
x = x + 1
return x
blahblah(2,3)
Answer:
¶
For this question, answer in terms of both $m$ and $n$.
def bllllergh(n, m):
x = 0
for i in range(n):
for j in range(m):
for k in range(m):
x = x + 1
for i in range(n):
for j in range(n):
for k in range(m):
x = x + 1
return x
bllllergh(2,3)
Answer:
def log_cabin(n):
for i in range(n):
print('i = ', i)
for j in range(n//3):
print('j = ', j)
cabin(n)
print('-----------')
log_cabin(4)
Answer:
def oh_no(n):
i = 0
while i < n:
i = i - 1
Answer:
Exercise: Space Complexity¶
For each of the following functions, determine the space complexity as a function of the input $n$ using big-O notation and briefly justify your answer.
def foo(n):
x = np.random.rand(n)
y = np.random.rand(n)
total = 0
for x_i in x:
for y_i in y:
total += x_i*y_i
return total
Answer:
def bar(n):
x = np.zeros(1000)
x = x + n
return x
Answer:
def FUNCTION(n):
x = set()
for i in range(n):
for j in range(n):
x.add(j)
return x
Answer:
!jupyter nbconvert _01-py-complexity-big-O-practice.ipynb --to html --template classic --output 01-py-complexity-big-O-practice.html