Quiz 02

Let $f(n) = 3n^2 \log n$. True or False: $f(n) = O(n^3)$.

True False

Solution

True.

Since $\log n$ grows more slowly than $n$, we have $3n^2 \log n \leq 3n^2 \cdot n = 3n^3$ for all $n \geq 1$, so $f(n) = O(n^3)$. (In fact, $f(n) = \Theta(n^2 \log n)$.)

Problem #033

Consider the function $f(n) = 5n^2 - 100n + 100.$ Which of the following asymptotic bounds are true? Choose all that apply.

Solution

$\Omega(n)$, $\Theta(n^2)$, $O(n^2)$, $\Omega(n^2)$, and $O(n^3)$. Since $f(n) = \Theta(n^2)$, it is $O$ of anything that grows at least as fast as $n^2$ and $\Omega$ of anything that grows at most as fast as $n^2$. It is not $O(n)$ (and so not $\Theta(n)$), and it is not $\Omega(n^3)$ (and so not $\Theta(n^3)$).

Problem #034

Let $f(n) = \displaystyle\frac{n^3 - 2n^2 + 100}{n + 10}$ True or False: $f(n) = O(n^4)$

True False

Solution

True.

The leading term of the numerator is $n^3$ and the leading term of the denominator is $n$, so $f(n) = \Theta(n^2)$. Anything that is $\Theta(n^2)$ is also $O(n^4)$, since $O$ only gives an upper bound.

Problem #035

Consider the function defined below:

\[ f(n) = \begin{cases} 3n, & \text{if $n$ is even;}\\ 5n ,& \text{if $n$ is odd.} \end{cases}\]

True or False: $f(n) = \Theta(n)$.

True False

Solution

True.

For every $n$, $3n \leq f(n) \leq 5n$, so $f(n)$ is bounded above and below by constant multiples of $n$. It doesn't matter that $f$ jumps between two different constants.

Problem #036

Consider the function $f(n) = \sin(12 n) \cdot\cos(n) + 2$. A plot of this function is shown below:

True or False: this function is $\Theta(1)$.

True False

Solution

True. This function is upper bounded by 3 and lower bounded by 1 for all $n$, and is therefore $\Theta(1)$.

Problem #037

Consider the function $f(n) = \sin(12n) \cdot\cos(n) + 2$. A plot of this function is shown below:

True or False: $f(n) = O(n^3)$.

True False

Solution

True. We saw that this function is $\Theta(1)$, but it is also correct to say that it is $O(n^3)$, though this is not a tight upper bound.

Problem #038

Tags: asymptotic notation, lecture-04

Suppose Algorithm A takes $\Theta(n^2)$ time, while Algorithm B takes $\Theta(2^n)$ time. True or False: there could exist an input on which Algorithm $B$ takes less time than Algorithm A.

True False

Solution

True.

Asymptotic notation only describes how the time grows for large $n$ and hides constants. For example, if A takes $1000n^2$ steps and B takes $2^n$ steps, then B is faster on every input of size $n = 10$(1024 steps vs. 100,000).

Problem #039

Tags: asymptotic notation, lecture-04

Suppose algorithm A takes $\Theta(n^2)$ time, while algorithm B takes $\Theta(n^3)$ time.

True or False: there must exist an input of size 100 on which Algorithm A takes less time than Algorithm B.

Solution

False. Algorithm A could have really large constants. For example, it could take 1,000,000 $n^2$ seconds to run, while algorithm B takes $.0001 n^3$ seconds to run. Algorithm B will still be better for $n = 100$.

Problem #040

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

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

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

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

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)$.

True False

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 #045

Consider the function $f(n) = \frac{n^8 + 2^{3 + \log n} - \sqrt n}{20 n^5 - n^2}$.

True or False: $f(n) = O(n^{4})$.

True False

Solution

True.

Note that $2^{3 + \log n} = 8 \cdot 2^{\log n} = 8n$, so the dominant term in the numerator is $n^8$, while the dominant term in the denominator is $20n^5$. Therefore $f(n) = \Theta(n^3)$, which is $O(n^4)$.

Problem #046

Consider the function $f(n) = \frac{n^8 + 2^{3 + \log n} - \sqrt n}{20 n^5 - n^2}$.

True or False: $f(n) = \Omega(n^2)$.

True False

Solution

True.

Since $2^{3 + \log n} = 8n$, the numerator is dominated by $n^8$ and the denominator by $20n^5$, so $f(n) = \Theta(n^3)$. Anything that is $\Theta(n^3)$ is also $\Omega(n^2)$, since $\Omega$ only gives a lower bound.

Problem #047

Let

\[ f(n) = \frac{n^3 - 2n + 100}{\sqrt n}\cdot\frac{n}{n^3 + n^2 + \sin n}\cdot n^2 \]

True or False: $f(n) = \Theta(n^2)$.

True False

Solution

False.

Keeping only the dominant terms, the first factor is $\Theta(n^3 / \sqrt n) = \Theta(n^{2.5})$ and the second is $\Theta(n / n^3) = \Theta(1/n^2)$. Multiplying by $n^2$ gives $f(n) = \Theta(n^{2.5})$, which is not $\Theta(n^2)$(it is not $O(n^2)$).

Problem #048

Let

\[ f(n) = \frac{n^3 + 10 n}{\sqrt{n} - 100}\times\frac{ \log(n^2 + 10)}{n(n+1)}\]

Write $f(n)$ in asymptotic notation in the simplest terms possible.

Solution

$f(n) = \Theta(\sqrt n \log n)$

Problem #049

Let

\[ f(n) = 5 n \log n + \frac{n^3 + 5}{n + 2 + |\sin \pi n|} + n \sqrt n \]

Write $f$ in asymptotic notation in as simplest terms possible.

Solution

$f(n) = \Theta(n^2)$

Problem #050

Let

Define $f(n) = f_1(n) \times f_2(n) \times f_3(n)$. What is $f(n)$, in asymptotic notation, in simplest terms possible?

Solution

$\Theta(n^3)$

Problem #051

Let $f(n) = n \cdot(\sin{n} + 1 )$. A plot of this function is shown below.

True or False: $f(n) = \Theta(n)$.

True False

Solution

False.

Remember that for $f(n)$ to be $\Theta(n)$, it has to be both upper- and lower-bounded by some positive constant times $n$. This function is upper bounded by $O(n)$, but it doesn't have a lower bound of $\Omega(n)$. Therefore, it can't be $\Theta(n)$.

In other words, there is no positive constant $c$ and no positive number $N$ such that $f(n) > c n$ for all $n > N$.

If you had to describe this function in asymptotic notation, you could say that $f(n) = O(n)$(and that would be a tight upper bound), but there is no lower bound, since the function keeps coming back down to zero.

Problem #052

Consider the function $f(n) = n \times(\sin(n) + 1)$. A plot of this function is shown below:

True or False: this function is $O(1 + \sin n)$.

True False

Solution

False.

$f(n)$ grows arbitrarily large, while $\sin n + 1$ is bounded above by 2.

More formally, there is no constant $c$ such that $c (1 + \sin n)$ upper bounds $f(n)$ for all large $n$.

Problem #053

Consider the function $f(n) = n \times( \sin(n) + 1)$. A plot of this function is shown below:

True or False: $f(n) = O(n^3)$.

True False

Solution

True.

Since $\sin(n) + 1$ is always between 0 and 2, we have $0 \leq f(n) \leq 2n$, so $f(n) = O(n)$ and therefore also $O(n^3)$. (The oscillation only prevents $f$ from being $\Omega(n)$; it doesn't affect the upper bound.)

Problem #054

Let $f$ be the piecewise function defined as:

\[ f(n) = \begin{cases} 1, & \text{if $n$ is a multiple of 1 million},\\ n^2, &\text{otherwise}. \end{cases}\]

If you were to plot $f$, the function would look like $n^2$, but would have point discontinuities where it ``jumps'' back to 1 whenever $n$ is a multiple of 1 million.

True or False: $f(n) = \Theta(n^2)$.

True False

Solution

False.

$f(n)$is upper bounded by $O(n^2)$, but it doesn't have a lower bound of $\Omega(n^2)$, which is necessary for it to be $\Theta(n^2)$.

To see why, remember that for $f(n)$ to be $\Omega(n^2)$, there must be a positive constant $c$ so that $f(n)$ stays above $c\cdot n^2$ for all $n$ greater than some $n_0$, meaning that it goes above $c n^2$and it stays above $c n^2$ forever, after some point.

Pick whatever positive $c$ you'd like -- the function $c\cdot n^2$ grows larger and larger as $n$ increases, and eventually becomes larger than 1. But the function $f(n)$ keeps dipping down to 1, meaning that it doesn't stay above $c\cdot n^2$ for all $n$ when $n$ is large. Therefore, $f(n)$ is not $\Omega(n^2)$, and therefore also not $\Theta(n^2)$.

Problem #055

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

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 #057

Let $f(n) = n^{ \frac{1}{\log_2(n)} } \times n.$ Which of the following asymptotic bounds on $f$ is true?

Hint: you might want to review your log properties. One useful one may be $\log_b c = 1 / \log_c b$.

Solution

$\Theta(n)$. Using $\frac{1}{\log_2 n} = \log_n 2$, we get $n^{1/\log_2 n} = n^{\log_n 2} = 2$. So $f(n) = 2n = \Theta(n)$.

Problem #058

Let $f(n) = 12 \log_2(3^{(n^2 - 2n)} + 2^{(\log n)} - 10n^2 - \log_3 n).$ Which of the following asymptotic bounds on $f$ is true?

Solution

$\Theta(n^2)$. Inside the logarithm, the term $3^{(n^2 - 2n)}$ dominates the others (which grow at most like $n^2$), so for large $n$ the argument is between $\frac{1}{2} \cdot 3^{(n^2 - 2n)}$ and $2 \cdot 3^{(n^2 - 2n)}$. Taking $\log_2$, $f(n)$ is within a constant of $12 (n^2 - 2n) \log_2 3$, which is $\Theta(n^2)$.

Problem #059

Suppose $f_1(n)$ is $O(n^2)$ and $\Omega(n)$. Also suppose that $f_2(n) = \Theta(n^2)$.

Consider the function $f(n) = f_1(n) + f_2(n)$. True or false: it must be the case that $f(n) = \Theta(n^2)$.

True False

Solution

True.

The upper bound: both $f_1$ and $f_2$ are $O(n^2)$, so their sum is $O(n^2)$. The lower bound: $f_1$ is nonnegative (for large $n$), so $f_1(n) + f_2(n) \geq f_2(n)$, which is $\Omega(n^2)$.

Problem #060

Suppose $f(n)$ is both $O(n^2)$ and $\Omega(n)$, and suppose $g(n) = \Theta(n^3)$. What are the tightest possible asymptotic bounds that can be placed on $f + g$?

If the upper and lower bounds are the same, you may use $\Theta$. If the upper and lower bounds are different, you should state them separately using $O$ and $\Omega$.

Solution

$\Theta(n^3)$

Problem #061

Suppose $f(n)$ is both $O(n^2)$ and $\Omega(n)$, and suppose $g(n) = \Theta(n^3)$. What are the tightest possible asymptotic bounds that can be placed on the product, $f \times g$?

If the upper and lower bounds are the same, you may use $\Theta$; otherwise you should use $O$ and $\Omega$.

Solution

$O(n^5)$ and $\Omega(n^4)$

Problem #062

Suppose $f_1(n)$ is $O(n^3)$ and $\Omega(n)$. Also suppose that $f_2(n) = O(n^2)$ and $\Omega(\sqrt n)$.

Consider the function $f(n) = f_1(n) + f_2(n)$. True or false: it must be the case that $f(n) = \Omega(n)$.

True False

Solution

True.

Both functions are nonnegative (for large $n$), so $f_1(n) + f_2(n) \geq f_1(n)$, and $f_1(n) = \Omega(n)$. Adding a nonnegative function can only make the sum bigger, so it can't hurt a lower bound.

Problem #063

Suppose that $f_1(n)$ is $O(n^3)$ and $\Omega(n)$. Also suppose that $f_2(n) = O(n^2)$ and $\Omega(\sqrt n)$.

Consider the function $g(n) = f_2(n) / f_1(n)$. Give the tightest possible upper bound on $g(n)$:

Solution

$O(n)$

Problem #064

Suppose $f_1(n)$ is $O(n^3)$ and $\Omega(n^2)$. Also suppose that $f_2(n)$ is $O(n^4)$ and $\Omega(n)$.

Consider the function $f(n) = f_1(n) + f_2(n)$. True or false: it must be the case that $f(n) = \Omega(n^2)$.

True False

Solution

True.

Both functions are nonnegative (for large $n$), so $f_1(n) + f_2(n) \geq f_1(n)$, and $f_1(n) = \Omega(n^2)$. The weaker lower bound on $f_2$ doesn't matter, since adding $f_2$ can only make the sum larger.

Problem #065

Suppose that $f_1(n)$ is $O(n^3)$ and $\Omega(n^2)$. Also suppose that $f_2(n)$ is $O(n^4)$ and $\Omega(n)$.

Consider the function $g(n) = f_2(n) / f_1(n)$. Give the tightest possible upper bound on $g(n)$:

Solution

$O(n^2)$

Problem #066

True or False. If $f = \Omega(n^5)$ and $f = O(n^7)$ then $f$ must be either $\Theta(n^5)$, or $\Theta(n^6)$, or $\Theta(n^7)$.

Solution

False. Counterexample: $f = n^{6.5}$. This is neither $\Theta(n^5)$ or $\Theta(n^6)$ or $\Theta(n^7)$; it is $\Theta(n^{6.5})$.

Problem #067

Suppose $f_1(n) = O(g_1(n))$ and $f_2(n) = \Omega(g_2(n))$. True or False: it is necessarily the case that $f_1 + f_2 = O(g_1(n))$.

True False

Solution

False.

We know nothing about how large $f_2$ can be, so it can dominate the sum. For example, take $f_1(n) = g_1(n) = g_2(n) = 1$ and $f_2(n) = n^2$. Then $f_2 = \Omega(1)$, but $f_1(n) + f_2(n) = 1 + n^2$ is not $O(1)$.

Problem #068

Suppose $f(n) = \Omega(n^3)$ and $g(n) = \Omega(n)$.

True or False: it is necessarily the case that $f/g = \Omega(n^2)$.

True False

Solution

False. Take $f(n) = n^3$ and $g(n) = n^3$. We can see from definition that $f(n) = \Omega(n^3)$ and $g(n) = \Omega(n)$. However,

\[\frac{f}{g}(n) = 1 \neq\Omega(n^2). \]

The key takeaway for this question is, since $g$ is on the denominator, we can make it grow arbitrarily fast, so that $f/g$ do not meet the requirements that we want.

Problem #069

Suppose $f_1(n)$ is $O(n^2)$ and $\Omega(n)$. Also suppose that $f_2(n) = \Theta(n^2)$.

Consider the function $g(n) = f_2(n) / f_1(n)$. True or false: it must be the case that $g(n) = \Omega(n)$.

True False

Solution

False.

$f_1$ could be as large as $n^2$. For example, if $f_1(n) = f_2(n) = n^2$, then $g(n) = 1$, which is not $\Omega(n)$. (We only know $g(n) = \Omega(1)$ and $g(n) = O(n)$.)

Problem #070

True or False. If $f_1 = \Theta(g_1(n))$ and $f_2 = O(g_2(n))$ then $\frac{f_1}{f_2} = \Theta(g_1 / g_2)$.

Solution

False. Try breaking it with a counterexample. What if $f_1 = n^3$, $f_2 = n^2$, $g_1 = n^3$ and $g_2 = n^3$. All of the conditions are satisfied, but $f_1/f_2 = n$, while $g_1/g_2 = 1$, so $f_1 / f_2$ is not $\Theta(g_1/g_2)$.

Problem #071

Suppose $f_1(n) = O(g_1(n))$ and $f_2 = O(g_2(n))$. Define $f(n) = \min\{ f_1(n), f_2(n) \}$ and $g(n) = \min\{ g_1(n), g_2(n) \}$. True or false, it is necessarily the case that $f(n) = O(g(n))$.

True False

Solution

True.

For large $n$, $f_1(n) \leq c_1 g_1(n)$ and $f_2(n) \leq c_2 g_2(n)$. The minimum of $f_1$ and $f_2$ is at most each of them, so with $c = \max\{c_1, c_2\}$ we get $\min\{f_1(n), f_2(n)\}\leq c \, g_1(n)$ and $\leq c \, g_2(n)$, i.e., $f(n) \leq c \min\{g_1(n), g_2(n)\}$.

Problem #072

Suppose $f_1(n) = \Omega(g_1(n))$ and $f_2 = \Omega(g_2(n))$. Define $f(n) = \min\{ f_1(n), f_2(n) \}$ and $g(n) = \min\{ g_1(n), g_2(n)\}$.

True or false: it is necessarily the case that $f(n) = \Omega(g(n))$.

True False

Solution

True.

For large $n$, $f_1(n) \geq c_1 g_1(n)$ and $f_2(n) \geq c_2 g_2(n)$. Letting $c = \min\{c_1, c_2\}$, whichever of $f_1(n)$ or $f_2(n)$ is smaller is still at least $c$ times the corresponding $g$, which is at least $c \min\{g_1(n), g_2(n)\}$. So $f(n) \geq c \, g(n)$.

Problem #073

Suppose $f_1(n) = \Omega(g_1(n))$ and $f_2 = \Omega(g_2(n))$. Define $f(n) = \max\{ f_1(n), f_2(n) \}$ and $g(n) = \max\{ g_1(n), g_2(n)\}$.

True or false: it is necessarily the case that $f(n) = \Omega(g(n))$. In other words, it must be the case that $\max\{ f_1(n), f_2(n) \} = \Omega( \max\{ g_1(n), g_2(n) \}) $

True False

Solution

True.

For large $n$, $f_1(n) \geq c_1 g_1(n)$ and $f_2(n) \geq c_2 g_2(n)$. Letting $c = \min\{c_1, c_2\}$, $\max\{f_1(n), f_2(n)\}$ is at least both $c\, g_1(n)$ and $c\, g_2(n)$, so it is at least $c \max\{g_1(n), g_2(n)\}$.

Problem #074

Which of the below is a tight theoretical lower bound for the problem of finding a mode of a collection of $n$ numbers?

Solution

$\Theta(n)$. In the worst case, all numbers are distinct and we must loop through all of them to discover this, taking linear time.

Problem #075

Suppose you are given a (possibly unsorted) array containing $n$ elements. Each element is either zero or one. You are tasked with determining if the majority (at least half) of the array's elements are one.

What is the tight theoretical lower bound for the worst case time complexity of this problem?

Solution

$\Theta(n)$

Problem #076

What is the best case time complexity of the following code?

def insertion_sort(arr):
    """Sort `arr` in ascending order."""
    n = len(arr)
    for i in range(1, n):
        x = arr[i]
        j = i - 1
        # find where to place x
        while j >= 0 and x < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = x

Solution

$\Theta(n)$. The best case occurs when the array is already sorted. Notice that in this case, the while loop will never actually execute.

Problem #077

What is the worst case time complexity of the following code?

def insertion_sort(arr):
    """Sort `arr` in ascending order."""
    n = len(arr)
    for i in range(1, n):
        x = arr[i]
        j = i - 1
        # find where to place x
        while j >= 0 and x < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = x

Solution

$\Theta(n^2)$. The worst case occurs when the array is sorted in reverse order. In this case, the while-loop executes on every iteration of the for-loop, and must move x from its current position all the way to the beginning of the array.

Problem #078

What is the best case time complexity of the following function?

def foo(arr):
    """arr is an array of size n"""
    for x in arr:
        for y in arr:
            if sum([x,y]) == 5:
                return sum(arr)
    return False

Solution

$\Theta(n)$. In the best case, we return sum(arr) on the very first iteration.

Problem #079

What is the worst case time complexity of the following function?

def foo(arr):
    """arr is an array of size n"""
    for x in arr:
        for y in arr:
            if sum([x,y]) == 5:
                return sum(arr)
    return False

Solution

$\Theta(n^2)$. In the worst case, we never find x + y == 5, and go through all $\Theta(n^2)$ iterations just to return False at the end.

Problem #080

What is the best case time complexity of the following function in terms of $n$?

def foo(arr):
    """`arr` is a list containing n numbers."""
    previous = None
    n = len(arr)
    for x in arr:
        if x == previous:
            for i in range(n**2):
                print('Equal!')
            return
        previous = x

Solution

$\Theta(n)$

Problem #081

What is the best case time complexity of the following function in terms of $n$?

def foo(arr):
    """`arr` is a list containing n numbers."""
    previous = None
    n = len(arr)
    for x in arr:
        if x == previous:
            for i in range(n**2):
                print('Equal!')
            return
        previous = x

Solution

$\Theta(n)$

Problem #082

What is the worst case time complexity of the following function in terms of $n$?

def foo(arr):
    """`arr` is a list containing n numbers."""
    previous = None
    n = len(arr)
    for x in arr:
        if x == previous:
            for i in range(n**2):
                print('Equal!')
            return
        previous = x

Solution

$\Theta(n^2)$

Problem #083

Suppose you are given a (possibly unsorted) array of $n$ floating point numbers and are tasked with counting the number of elements in the array which are within ten of the array's maximum (you are not told the maximum). That is, you must count the number of elements $x$ such that $m - x \geq 10$, where $m$ is the array's maximum. You may assume that the array does not contain duplicate numbers.

What is the tight theoretical lower bound for the worst case time complexity of this problem?

Solution

$\Theta(n)$.

It takes $\Theta(n)$ time to find the maximum. After this, we loop through and keep track of how many elements are within ten of the maximum -- this also takes $\Theta(n)$ time.

Problem #084

The below code takes in an array of numbers and returns the index of the first maximum. What is this code's best case time complexity?

def index_of_maximum(arr):
    """`arr` is an array with n elements."""
    for i, x in enumerate(arr):
        if x == max(arr):
            return i

Solution

$\Theta(n)$

Problem #085

The below code takes in an array of numbers and returns the index of the first maximum.

def foo(arr):
    """`arr` is an array with n elements."""
    for i, x in enumerate(arr):
        if x == max(arr):
            return i

What is the worst case time complexity of the function?

Solution

$\Theta(n^2)$

Problem #086

The code below takes in an array of $n$ numbers and checks whether there is a pair of numbers in the array which, when added together, equal the maximum element of the array.

What is the best case time complexity of this code as a function of $n$? State your answer using asymptotic notation.

def exists_pair_summing_to_max(arr):
    n = len(arr)
    maximum = max(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == maximum:
                return True
    return False

Solution

$\Theta(n)$

Problem #087

What is the expected time complexity of the following function?

import random

def foo(n):
    # randomly draw a number from 0, 1, 2, ..., n-1
    x = random.randint(0, n-1)
    if x == 1:
        for i in range(n):
            print(i)
    else:
        print("lucky!")

    for i in range(n):
        print(i)

Solution

$\Theta(n)$. The last loop always runs $n$ times. With probability $1/n$ we have x == 1, and the first loop also runs, taking $\Theta(n)$ time; otherwise we do constant work before the last loop. So the expected time is $\frac{1}{n} \cdot \Theta(n) + \Theta(1) + \Theta(n) = \Theta(n)$. (In fact, every case takes $\Theta(n)$ time.)

Problem #088

Tags: time complexity, lecture-04

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 #089

What is the expected time complexity of the function below?

import random

def foo(n):
    # draw a random number uniformly from 0, 1, 2, ..., 99
    # in constant time
    x = random.randrange(100)
    for i in range(x):
        for j in range(n):
            print("Here!")

Solution

$\Theta(n)$. Note that in this question, the range of $x$ is between 0 and 99. Therefore the outer loop will run a constant number of times no matter what $x$ is. Then we can focus on the inner loop, which runs for $n$ times the print() operation, which is $\Theta(n)$ time. Therefore, the expected time complexity for this piece of code is $\Theta(n)$.

Problem #090

Tags: lecture-04, theoretical lower bounds, sorted structure

Suppose you are given a sorted array containing $n$ elements. Each element is either zero or one. You are tasked with determining if the majority (at least half) of the array's elements are one. What is the tight theoretical lower bound for the worst case time complexity of any algorithm which solves this problem?

Solution

$\Theta(1)$

Problem #091

The code below takes in two lists, each containing $n$ integers, and determines if the any number in the second list appears at least $n/2$ times in the first list.

def boo(first_list, second_list):
    """first_list and second_list are both of size n"""
    n = len(first_list)
    for x in second_list:
        count = 0
        for y in first_list:
            if x == y:
                count += 1
            if count >= n // 2:
                return True
    return False

Part 1)

What is the best case time complexity of this code as a function of $n$? State your answer using asymptotic notation.

Solution

$\Theta(n)$

Part 2)

What is the worst case time complexity of this code as a function of $n$? State your answer using asymptotic notation.

Solution

$\Theta(n^2)$

Solution

The best case is when the first element of the second list appears at least $n/2$ times in the first list. In this case, the code will return True after iterating $n/2$ times through the inner loop, taking $\Theta(n)$ time total.

In the worst case, there is no element in the second list that appears $n/2$ times in the first. We make all $n$ iterations of the outer loop, and during each of the outer iterations, make $n$ iterations of the inner loop, for a total of $\Theta(n^2)$ time.

Problem #092

The code below takes in two lists, each containing $n$ integers.

def are_lists_equal(list1, list2):
    if len(list1) != len(list2):
        return False
    for i in range(len(list1)):
        if list1[i] != list2[j]:
            return False
    return True


def foo(list1, list2):
    if are_lists_equal(list1, list2):
        for i in list1:
            print(i)
    else:
        for i in list1:
            for j in list2:
                for k in range(len(list1)):
                    print(i, j, k)

What is the best case time complexity of foo as a function of $n$? State your answer using asymptotic notation.

Solution

The best case is where the lists are equal. In this case the time complexity is $\Theta(n)$. The worst case is when the lists are not equal in which case the time complexity is $\Theta(n^3)$.

Problem #093

What is the expected time complexity of the function below?

import random

def foo(n):
    # draw a random number uniformly from 0, 1, 2, ..., n-1
    # in constant time
    x = random.randrange(n)
    for i in range(x):
        for j in range(n):
            print("Here!")

Solution

$\Theta(n^2)$. The inner loop is not random, and the time complexity of it is always $\Theta(n)$. Therefore the expected time complexity of this function will be (using the arithmetic sequence sum formula)

\[\frac{1}{n}\sum_{i = 0}^{n - 1} i \times\Theta(n) = \Theta(n^2). \]

Problem #094

What is the expected time complexity of the following function?

import random

def foo(n):
    for i in range(n):
        # draw a number uniformly at random from 0, 1, 2, ..., n-1 in Theta(1)
        x = random.randrange(n)
        for j in range(x):
            print(j)

Solution

$\Theta(n^2)$. For this function, the outer loop wil execute $n$ times no matter what, hence we only have to find what the expected time complexity for the inner loop is, then combine that together with the outer loop. For the inner loop, the expected time complexity is

\[\frac{1}{n}\sum_{i = 1}^{n - 1} i = \frac{1}{n}\cdot\Theta(n^2) = \Theta(n). \]

Then, the expected complexity for the whole function will be

\[\Theta(n) \times\Theta(n) = \Theta(n^2). \]

Problem #095

What is the expected time complexity of the function below?

import random

def foo(n):
    # draw a number uniformly at random from 0, 1, 2, ..., n-1
    # in constant time
    x = random.randrange(n)
    if x < 100:
        for j in range(n**2):
            print(j)

Solution

$\Theta(n)$. The for loop is only executed if $x$ is less than 100, therefore we can write the expected time as (ignoring constants $c$):

\[ f(n) = \frac{1}{n}\bigg(\sum_{i = 0}^{99} n^2 + \sum_{i = 100}^{n - 1} 1 \bigg)= \frac{1}{n}\cdot(\Theta(n^2) + \Theta(n)) = \Theta(n). \]

Problem #096

What is the expected time complexity of the following function? State your answer using asymptotic notation.

import random

def foo(n):
    x = random.randrange(n)

    if x < 8:
        for j in range(n**3):
            print(j)
    else:
        for j in range(n):
            print(j)

Solution

$\Theta(n^2)$. The expected time complexity for this function is

\[\frac{1}{n}\bigg(\sum_{i = 0}^{7} n^3 + \sum_{i = 8}^{n - 1} n \bigg)= \frac{1}{n}(\Theta(n^3) + \Theta(n^2)) = \Theta(n^2). \]

Problem #097

Tags: time complexity, lecture-04

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 #098

What is the expected time complexity of the function below?

import random

def foo(n):
    # draw a number uniformly at random from 0, 1, 2, ..., n-1 in Theta(1)
    x = random.randrange(n)
    if x < math.sqrt(n):
        for j in range(n):
            print(j)

Solution

$\Theta(\sqrt n)$. Since the for loop only executes when $x$ is less than $\sqrt{n}$, the expected time complexity is

\[\frac{1}{n}\bigg(\sum_{i = 1}^{\lfloor \sqrt{n} \rfloor} n + \sum_{i = \lceil \sqrt{n} \rceil}^{n - 1} 1 \bigg)\approx\frac{1}{n}(n \sqrt{n} + (n - \sqrt{n})) = \Theta(\sqrt{n}). \]

Problem #099

What is the expected time complexity of the function below?

You may assume that math.sqrt takes $\Theta(1)$ time.

import random
import math

def foo(n):
    # draw a number uniformly at random from 0, 1, 2, ..., n-1 in Theta(1)
    x = random.randrange(n)

    if x < math.sqrt(n):
        for j in range(n):
            print(j)
    elif x < n//2:
        print('Ok!')
    else:
        for i in range(n**2):
            print(i)

Solution

$\Theta(n^2)$. The expected time complexity for this function is

\[ f(n) = \frac{1}{n}\bigg(\sum_{i = 1}^{\lfloor \sqrt{n} \rfloor} n + \sum_{i = \lceil \sqrt{n} \rceil}^{\lfloor n/2 \rfloor} 1 + \sum_{i = \lceil n/2 \rceil}^{n - 1} n^2 \bigg) = \frac{1}{n}(\Theta(n \sqrt{n}) + \Theta(n) + \Theta(n^3)) = \Theta(n^2). \]

Problem #100

What is the expected time complexity of the function below? State your answer using asymptotic notation.

You may assume that math.sqrt and math.log2 take $\Theta(1)$ time.

import random
import math

def boo(n):
    # draw a number uniformly at random from 0, 1, 2, ..., n-1 in Theta(1)
    x = random.randrange(n)

    if x < math.log2(n):
        for i in range(n**2):
            print("Very unlucky!")
    elif x < math.sqrt(n):
        for i in range(n):
            print("Unlucky!")
    else:
        print("Lucky!")

Solution

$\Theta(n \log n)$ There are three cases: Case 1) $x < \log_2 n$; Case 2) $1 < x < \sqrt n$; and Case 3) $x \geq\sqrt{n}$.

The probability of Case 1 is $\log n / n$. The time taken in case 1 is $\Theta(n^2)$.

The probability of Case 2 is

\[\frac{\sqrt n}{n} - \frac{\log_2 n}{n} = \Theta(\sqrt n / n) = \Theta(1/\sqrt n). \]

The time taken in this case is $\Theta(n)$.

The probability of Case 3 is 1 minus the probability of the sum of the other two cases, which will simply be $\Theta(1)$:

\[ 1 - \Theta(1 / n) - \Theta(1 / \sqrt{n}) = \Theta(1). \]

The time taken is $\Theta(1)$.

Therefore, the expected time is:

Problem #101

What is the expected time complexity of the function below? State your answer using asymptotic notation.

You may assume that math.sqrt and math.log take $\Theta(1)$ time. math.log computes the natural log.

import random
import math

def foo(n):
    # draw a number uniformly at random from 0, 1, 2, ..., n-1 in Theta(1)
    x = random.randrange(n)

    if x < math.log(n):
        for j in range(n**2):
            print(j)
    elif x < math.sqrt(n):
        print('Ok!')
    else:
        for i in range(n):
            print(i)

Solution

$\Theta(n \log n)$ There are three cases: Case 1) $x < \log n$; Case 2) $\log n \geq x < \sqrt n$; and Case 3) $x \geq\sqrt{n}$.

The probability of Case 1 is $\log n / n$. The time taken in case 1 is $\Theta(n^2)$.

The probability of Case 2 is

\[\frac{\sqrt n}{n} - \frac{\log n}{n} = \Theta(\sqrt n / n) = \Theta(1/\sqrt n). \]

The time taken in this case is $\Theta(1)$.

The probability of Case 3 is 1 minus the probability of the sum of the other two cases, which will simply be $\Theta(1)$:

\[ 1 - \Theta((\log n) / n) - \Theta(1 / \sqrt{n}) = \Theta(1) \]

Therefore, the expected time is:

\[\begin{aligned} \frac{\log n}{n} \times \Theta(n^2) + \Theta(1/\sqrt n) \times \Theta(1) + \Theta(1) \times \Theta(n) &= \Theta(n \log n) + \Theta(1 / \sqrt n) + \Theta(n) \\ &= \Theta(n \log n) \end{aligned}\]

Problem #102