Practice problems for topics on Quiz 01.
Tags in this problem set:
Tags: time complexity, lecture-01
What is the time complexity of the following function?
def foo(arr):
"""`arr` is an array with n elements."""
x = max(arr) * min(arr)
if sum(arr) > 10:
return x
else:
return 0
\(\Theta(n)\)
Tags: time complexity, lecture-01
What is the time complexity of the following function?
def also_the_variance(data):
"""
computes the variance of `data`
`data` is a list of size n
"""
mu = sum(data) / len(data)
total = 0
for x in data:
total += (x - mu)**2
return total / len(data)
\(\Theta(n)\). sum(data) takes \(\Theta(n)\) time but is computed only once, before the loop. The loop runs \(n\) times and does constant work on each iteration.
Tags: time complexity, lecture-01
What is the time complexity of the following function?
def variance(data):
"""
computes the variance of `data`
`data` is a list of size n
"""
# compute the variance again
total = 0
for x in data:
mu = sum(data) / len(data)
total += (x - mu)**2
return total / len(data)
\(\Theta(n^2)\). sum(data) takes \(\Theta(n)\) time and is recomputed on each of the \(n\) iterations of the loop.
Tags: time complexity, lecture-01
What is the time complexity of the following function?
def foo(arr):
"""arr is an array of size n"""
n = len(arr)
for i in range(n):
r = sum(arr) * sum(arr)
print(r)
\(\Theta(n^2)\). Each iteration of the loop calls sum(arr) twice, and each call takes \(\Theta(n)\) time. The loop runs \(n\) times, so the total is \(\Theta(n^2)\).
Tags: time complexity, lecture-01
Suppose numbers is a list of integers of length \(n\). What is the time complexity of the following function in terms of \(n\)? State your answer using asymptotic notation (e.g., \(\Theta(n)\)) in the simplest terms possible.
def foo(numbers):
for x in numbers:
r = max(numbers) * min(numbers) * x
print(r)
\(\Theta(n^2)\)
Tags: time complexity, lecture-01
What is the time complexity of the following function in terms of \(n\)?
def foo(arr):
"""`arr` is a list containing n numbers."""
for x in arr:
if x > max(arr) / 2:
print('large!')
elif x < min(arr) * 2:
print('small!')
else:
print('neither!')
\(\Theta(n^2)\)
Tags: time complexity, lecture-01
What is the time complexity of the following function in terms of \(n\)?
def foo(arr):
"""`arr` is a list containing n numbers."""
for x in arr:
n = len(arr)
if x > sum(arr) / n:
print('large!')
elif x < sum(arr) / n:
print('small!')
else:
print('neither!')
\(\Theta(n^2)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function? State your answer using asymptotic notation (e.g., \(\Theta(n)\)).
def foo(n):
for i in range(n):
for j in range(n):
for k in range(n**2):
print(i + j + k)
\(\Theta(n^4)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function? State your answer using asymptotic notation (e.g., \(\Theta(n)\)).
def foo(n):
for i in range(n):
for j in range(n**2):
for k in range(n):
print(i + j + k)
\(\Theta(n^4)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function?
def foo(n):
for i in range(n**2 - 2*n + 100):
j = 0
while j < n:
j += 1
\(\Theta(n^3)\). The outer loop runs \(n^2 - 2n + 100 = \Theta(n^2)\) times, and on each of its iterations the inner while loop runs \(n\) times, for a total of \(\Theta(n^2) \cdot \Theta(n) = \Theta(n^3)\).
Tags: time complexity, lecture-02
What is the time complexity of the following function?
def foo(n):
total = 0
for i in range(n**2):
for j in range(n**2 + 5*n - 100):
for k in range(n // 1_000_000):
total += i**2 + n**2
return total
\(\Theta(n^5)\). The three loops run \(n^2\), \(n^2 + 5n - 100 = \Theta(n^2)\), and \(\lfloor n / 1{,}000{,}000 \rfloor = \Theta(n)\) times, and the loop body takes constant time, so the total is \(\Theta(n^2 \cdot n^2 \cdot n) = \Theta(n^5)\).
Tags: time complexity, lecture-02
What is the time complexity of the following function?
import math
def foo(n):
for i in range(math.floor(math.sqrt(n))):
for j in range(math.floor(5*n**2 - math.sqrt(n)/1_000_000 + 100)):
print(n * n)
\(\Theta(n^2 \sqrt n)\)
Tags: time complexity, lecture-02
Express the time complexity of the following code using asymptotic notation in as simplest terms possible.
def foo(n):
for i in range(n**3):
for j in range(n):
print(i + j)
for j in range(n**2):
print(i + j)
\(\Theta(n^5)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function in terms of \(n\)? State your answer using asymptotic notation (e.g., \(\Theta(n)\)).
def foo(n):
for i in range(n**3):
for j in range(n):
print(i + j)
for k in range(n):
for l in range(n**2):
print(k * l)
\(\Theta(n^4)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function in terms of \(n\)? State your answer using asymptotic notation (e.g., \(\Theta(n)\)) in the simplest terms possible.
import math
def foo(n):
for i in range(3 * n**3 + 5 * n * math.ceil(math.log(n))):
for j in range(math.floor(math.sqrt(n))):
print(i + j)
for k in range(n**2):
print(k * i)
\(\Theta(n^5)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function?
def foo(n):
while n > 1:
n /= 10
print(n)
\(\Theta(\log n)\). After \(k\) iterations, the value of n is \(n / 10^k\). The loop stops once this is at most 1, which happens after about \(\log_{10} n = \Theta(\log n)\) iterations.
Tags: time complexity, lecture-02
What is the time complexity of the following function? State your answer as a function of \(n\) using asymptotic notation in the simplest form possible. (e.g., \(\Theta(n)\))
import math
def boo(n):
i = n
while i > 1:
i = i / 2
for j in range(1_000_000):
print(i + j)
\(\Theta(\log n)\)
Tags: time complexity, lecture-02
Express the time complexity of the following code using asymptotic notation in as simplest terms possible.
import math
def foo(arr):
"""`arr` is an array with n elements."""
n = len(arr)
ix = 1
s = 0
while ix < n:
s = s + arr[ix]
ix = ix * 5 + 2
return s
\(\Theta(\log n)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function?
def foo(n):
i = 1
while i < n:
j = 0
while j < n:
j += 1
i *= 2
\(\Theta(n \log n)\). Since i doubles on each iteration, the outer loop runs \(\Theta(\log n)\) times. The inner loop runs \(n\) times on each of these, for a total of \(\Theta(n \log n)\).
Tags: time complexity, lecture-02
What is the time complexity of the following function in terms of \(n\)? State your answer using asymptotic notation (e.g., \(\Theta(n)\)) in the simplest terms possible.
def foo(n):
i = 1
while i < n**3:
i = i * 2
for j in range(n):
print(i + j)
\(\Theta(n\log n)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function in terms of \(n\)?
from math import sqrt, log, ceil
def foo(n):
for i in range(ceil(n**3 - 10*n + sqrt(n))):
for j in range(ceil(log(n**2))):
print(i, j)
\(\Theta(n^3 \log n)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function in terms of \(n\)? State your answer using asymptotic notation (e.g., \(\Theta(n)\)).
def foo(n):
i = 0
while i < n**2:
i = i + 2
j = 0
while j < n:
for k in range(n):
print(i + j + k)
j = j + 10
\(\Theta(n^4)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function in terms of \(n\)? State your answer using asymptotic notation (e.g., \(\Theta(n)\)) in the simplest terms possible.
def foo(n):
for i in range(n):
for j in range(2023):
for k in range(n - i):
print("DSC40B")
\(\Theta(n^2)\)
Tags: time complexity, lecture-02
Express the time complexity of the following code using asymptotic notation in as simplest terms possible.
def foo(n):
for i in range(n):
for j in range(i):
for k in range(n):
print(i + j + k)
\(\Theta(n^3)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function?
def foo(n):
for i in range(n):
for j in range(n):
for k in range(j): # ← notice the range!
print(j)
\(\Theta(n^3)\). For a fixed i, the two inner loops run \(0 + 1 + 2 + \ldots + (n-1) = n(n-1)/2 = \Theta(n^2)\) times in total. The outer loop runs \(n\) times, so the total is \(\Theta(n^3)\).
Tags: time complexity, lecture-02
What is the time complexity of the following function?
def foo(n):
i = 0
while i < n:
j = 0
while j < i:
print(i + j)
j += 1
i += 5
\(\Theta(n^2)\)
Tags: time complexity, lecture-02
Express the time complexity of the following code using asymptotic notation in as simplest terms possible.
def foo(n):
for i in range(200, n):
for j in range(i, 2*i + n**2):
print(i + j)
\(\Theta(n^3)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function? State your answer as a function of \(n\) using asymptotic notation in the simplest form possible. (e.g., \(\Theta(n)\))
def boo(n):
for i in range(200, n):
for j in range(i, i * n):
print(i + j)
If you count the number of times the inner loop body executes, you'll get something like \(n + 2n + 3n + \ldots + n\times n\). Factoring out the \(n\) and using the formula for the sum of the first \(n\) integers, we get \(n (1 + 2 + 3 + \ldots + n) = n \Theta(n^2) = \Theta(n^3)\).
Tags: time complexity, lecture-02
What is the time complexity of the following function in terms of \(n\)?
import math
def foo(n):
for i in range(math.floor(math.sqrt(n))):
for j in range(i):
print(i + j)
\(\Theta(n)\)
Tags: time complexity, lecture-02
What is the time complexity of the following function in terms of \(n\)?
def foo(n):
for i in range(n**2):
for j in range(i):
print(i+j)
for k in range(n):
print(i+k)
for x in range(n - i):
print(x)
\(\Theta(n^4)\)