Problems tagged with "time complexity"
Problem #001
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
Solution
\(\Theta(n)\)
Problem #002
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)
Solution
\(\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.
Problem #003
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)
Solution
\(\Theta(n^2)\). sum(data) takes \(\Theta(n)\) time and is recomputed on each of the \(n\) iterations of the loop.
Problem #004
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)
Solution
\(\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)\).
Problem #005
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)
Solution
\(\Theta(n^2)\)
Problem #006
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!')
Solution
\(\Theta(n^2)\)
Problem #007
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!')
Solution
\(\Theta(n^2)\)
Problem #008
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)
Solution
\(\Theta(n^4)\)
Problem #009
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)
Solution
\(\Theta(n^4)\)
Problem #010
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
Solution
\(\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)\).
Problem #011
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
Solution
\(\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)\).
Problem #012
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)
Solution
\(\Theta(n^2 \sqrt n)\)
Problem #013
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)
Solution
\(\Theta(n^5)\)
Problem #014
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)
Solution
\(\Theta(n^4)\)
Problem #015
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)
Solution
\(\Theta(n^5)\)
Problem #016
Tags: time complexity, lecture-02
What is the time complexity of the following function?
def foo(n):
while n > 1:
n /= 10
print(n)
Solution
\(\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.
Problem #017
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)
Solution
\(\Theta(\log n)\)
Problem #018
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
Solution
\(\Theta(\log n)\)
Problem #019
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
Solution
\(\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)\).
Problem #020
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)
Solution
\(\Theta(n\log n)\)
Problem #021
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)
Solution
\(\Theta(n^3 \log n)\)
Problem #022
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
Solution
\(\Theta(n^4)\)
Problem #023
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")
Solution
\(\Theta(n^2)\)
Problem #024
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)
Solution
\(\Theta(n^3)\)
Problem #025
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)
Solution
\(\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)\).
Problem #026
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
Solution
\(\Theta(n^2)\)
Problem #027
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)
Solution
\(\Theta(n^3)\)
Problem #028
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)
Solution
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)\).
Problem #029
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)
Solution
\(\Theta(n)\)
Problem #030
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)
Solution
\(\Theta(n^4)\)
Problem #031
Tags: time complexity
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):
for i in range(n):
for j in range(n**2 + 100, 500*n**3):
for k in range(1_000, math.floor(math.log(n))):
print(i + j + k)
Solution
\(\Theta(n^4 \log n)\)
Problem #040
Tags: time complexity
Suppose bar and baz are two functions. Suppose bar's time complexity is \(\Theta(n^3)\), while baz's time complexity is \(\Theta(n^2)\).
Suppose boo is defined as below:
def boo(n):
if n < 1000:
bar(n)
else:
baz(n)
What is the asymptotic time complexity of boo?
Solution
Asymptotic time complexity concerns the time taken when \(n\) is large. Therefore, it doesn't matter what happens when \(n < 1000\). When \(n \geq 1000\), the time taken is \(\Theta(n^2)\), since that is the time taken by baz.
Problem #041
Tags: time complexity
Suppose bar and baz are two functions. Suppose bar's time complexity is \(\Theta(n^3)\), while baz's time complexity is \(\Theta(n^2)\).
Suppose foo is defined as below:
def foo(n):
if n < 1_000:
bar(n)
else:
baz(n)
What is the asymptotic time complexity of foo?
Solution
\(\Theta(n^2)\)
Problem #042
Tags: time complexity
Suppose bar and baz are two functions. Suppose bar's asymptotic time complexity is \(\Theta(n^4)\), while baz's is \(\Theta(n)\).
Suppose foo is defined as below:
def foo(n):
if n < 1_000_000:
bar(n)
else:
baz(n)
What is the asymptotic time complexity of foo?
Solution
\(\Theta(n)\) If you were to plot the function \(T(n)\) that gives the time taken by foo as a function of \(n\), you'd see something like the below:
This function starts off looking like \(n^4\), but at \(n = 1_000_000\), it "switches" to looking like \(n\).
Since asymptotic time complexity is concerned with the behavior of the function as \(n\) gets large, we can ignore the part where \(n\) is "small" (in this case, less than \(1{,}000{,}000\)). So, asymptotically, this function is \(\Theta(n)\).
Problem #043
Tags: time complexity
Suppose bar_1, bar_2 and bar_3 are three functions. Suppose bar_1's time complexity is \(\Theta(n)\), bar_2's time complexity is \(\Theta(n^2)\), and bar_3's time complexity is \(\Theta(n^3)\).
Suppose foo is defined as below:
def foo(n):
if n < 2023:
bar_1(n**3)
elif n == 2023:
bar_3(n**2)
else:
bar_2(n)
What is the asymptotic time complexity of foo?
Solution
Asymptotic time complexity concerns the time taken when \(n\) is large. Therefore, it doesn't matter what happens when \(n < 1000\). When \(n \geq 1000\), the time taken is \(\Theta(n^2)\), since that is the time taken by bar_2.
Problem #044
Tags: time complexity
Suppose bar and baz are two functions. Suppose bar's time complexity is \(\Theta(n^2)\), while baz's time complexity is \(\Theta(n)\).
Suppose foo is defined as below:
def foo(n):
# will be True if n is even, False otherwise
is_even = (n % 2) == 0
if is_even:
bar(n)
else:
baz(n)
Let \(T(n)\) be the time taken by foo on an input of sized \(n\). True or False: \(T(n) = \Theta(n^2)\).
Solution
False.
This function is not \(\Theta(n^2)\). For that matter, it is also not \(\Theta(n)\). It is\(O(n^2)\) and \(\Omega(n)\), though.
This function cannot be \(\Theta(n^2)\) because there are no positive constants \(c, n_0\) such that \(T(n) > c n^2\) for all \(n > n_0\). You can see this by imagining the plot of the time taken by foo as a function of \(n\). It "oscillates" between something that grows like \(n\) and something that grows like \(n^2\). If you tried to lower bound it with \(cn^2\), \(T(n)\) would eventually dip below \(cn^2\), since \(cn^2\) grows faster than \(n\).
Problem #055
Tags: time complexity
What is the time complexity of the following function?
def foo(n):
for i in range(n):
for j in range(i**2): # <-- notice the bound!
print(i + j)
Solution
\(\Theta(n^3)\). The inner loop runs \(i^2\) times, so the total number of iterations is \(0^2 + 1^2 + \ldots + (n-1)^2 = \frac{(n-1)n(2n-1)}{6} = \Theta(n^3)\).
Problem #056
Tags: time complexity
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):
for i in range(n):
for j in range(n):
print(i + j)
for i in range(math.floor(math.sqrt(n))):
for j in range(math.log2(i), i * math.floor(math.log2(i + 10))):
print(i + j)
Solution
The second loop looks complicated to analyze, but we can effectively ignore it. This is because the most i can ever be is \(\sqrt
n\), and so an upper bound for the number of iterations made by the second loop is \(O(\sqrt n \log n)\). Since the first loop takes \(\Theta(n^2)\), it will dominate the time complexity, and we do not need to worry about the time taken by the second loop.
Problem #088
Tags: time complexity
What is the expected time complexity of the following function? State your answer using asymptotic notation.
import random
def boo(n):
# draw a number uniformly at random from 0, 1, 2, ..., n-1 in Theta(1)
x = random.randrange(n)
for i in range(x): # <-- note that the range is random!
print(i)
Solution
\(\Theta(n)\)
Problem #097
Tags: time complexity
What is the expected time complexity of the function below? State your answer using asymptotic notation.
import random
def foo(n):
# draw a number uniformly at random from 0, 1, 2, ..., n-1 in Theta(1) time
x = random.randrange(n)
if x < 20:
for i in range(n**3):
print("Very unlucky!")
elif x < n / 2:
for i in range(n):
print("Unlucky!")
else:
print("Lucky!")
Solution
\(\Theta(n^2)\).
Problem #136
Tags: time complexity
import math
def mediansort(arr, start, stop):
"""Claims to sort the array, in-place"""
if stop - start <= 1:
return
# finds the index of the median of arr[start:stop]
median_ix = find_median(arr, start, stop)
middle_ix = math.floor((start + stop) / 2)
# move the median to the middle by swapping
arr[median_ix], arr[middle_ix] = arr[middle_ix], arr[median_ix]
# recurse on the left and right halves
mediansort(arr, start, middle_ix)
mediansort(arr, middle_ix + 1, stop)
Consider the mediansort function from above. Suppose that find_median takes \(\Theta(n)\) time. What is the time complexity of mediansort?
Solution
\(\Theta(n \log n)\)
Problem #173
Tags: time complexity, binary search trees
Suppose a collection of unique numbers is stored in a balanced binary search tree, and that each node in the tree has been given a .size attribute which contains the number of nodes in the subtree rooted at that node. What is the time complexity required of an efficient algorithm for computing the number of elements in the collection which are larger than some threshold, \(t\)?
Solution
\(\Theta(\log{n})\). We can consider the following algorithm: Query for \(t\) in the BST, and define a new variable total for tracking the result. For each step of the recursion, if we go to the left, add the size of the right branch + 1 to the running total. We repeat the above until the query() function finishes running, which will give us exactly the number of elements in the collection which are larger than \(t\). Since we are querying (and adding some constant time updating steps) in a balanced BST, the time complexity for this question will be \(\Theta(\log{n})\).
Problem #237
Tags: time complexity, breadth first search
Suppose an undirected graph with \(n\) nodes satisfies the property that every node has degree \(n/2\). What is the time complexity of running full BFS on this graph?
Solution
\(\Theta(n^2)\). Full BFS takes \(\Theta(V + E)\) time. The sum of the degrees is \(n \cdot n/2\), and each edge is counted twice in this sum, so there are \(n^2/4\) edges. So the time is \(\Theta(n + n^2/4) = \Theta(n^2)\).
Problem #242
Tags: time complexity, aggregate analysis, breadth first search
Consider the following modification of BFS, where there are two new lines of code. What is the time complexity in terms of \(|V|\) and \(|E|\)?
from collections import deque
def foo(graph):
status = {node: 'undiscovered' for node in graph.nodes}
for u in graph.nodes:
if status[u] == 'undiscovered':
bar(graph, u, status)
def bar(graph, source, status):
status[source] = 'pending'
pending = deque([source])
# while there are still pending nodes
while pending:
u = pending.popleft()
for v in graph.neighbors(u):
# explore edge (u,v)
if status[v] == 'undiscovered':
status[v] = 'pending'
pending.append(v)
for v in graph.nodes:
print(v)
status[u] = 'visited'
Solution
\(\Theta(V + VE)\). Without the two new lines, this is a full BFS, which takes \(\Theta(V + E)\) time. The new inner loop runs once each time an edge is explored, and each time it takes \(\Theta(V)\) time. By an aggregate analysis, edges are explored \(\Theta(E)\) times in total, so the new lines add \(\Theta(VE)\) time. The total is \(\Theta(V + E + VE) = \Theta(V + VE)\). (We can't drop the \(V\) term: when there are no edges, the code still takes \(\Theta(V)\) time.)