Midterm 01

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

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

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

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

What is the worst case time complexity of the function in the previous problem?

Solution

$\Theta(n^2)$

Problem #007

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

Tags: sorted structure, theoretical lower bounds

Consider the same problem as above, except now you may assume that the array is sorted. What is the tight theoretical lower bound for the worst case time complexity of any algorithm which solves this problem?

Solution

$\Theta(1)$

Problem #009

Tags: expected time

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

Problem #010

Tags: expected time

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

Problem #011

State (but do not solve) the recurrence describing the run time of the following code, assuming that the input, arr, is a list of size $n$.


def foo(arr, stop=None):
    if stop is None:
        stop = len(arr) - 1

    if stop < 0:
        return 1

    last = arr[stop]
    return last * foo(arr, stop - 1)

Solution

$T(n) = T(n-1) + \Theta(1)$

Problem #012

What is the solution of the below recurrence? State your answer using asymptotic notation as a function of $n$.

\[ T(n) = \begin{cases} 5 T(n/5) + \Theta(n),& n > 1\\ 1,& n = 1 \end{cases}\]

Solution

$\Theta(n \log n)$

Problem #013

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

True False

Solution

True.

Problem #014

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.

Problem #015

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

Tags: binary search

Consider the code below, which shows binary_search as discussed in lecture, but with one additional line: a print statement.


import math
def binary_search(arr, t, start, stop):
    if stop - start <= 0:
        return None
    middle = math.floor((start + stop)/2)
    print(arr[middle]) # <---- this line is new
    if arr[middle] == t:
        return middle
    elif arr[middle] > t:
        return binary_search(arr, t, start, middle)
    else:
        return binary_search(arr, t, middle+1, stop)

Suppose this version of binary search is called on an array and with a target of t = 7. Which of the following statements is true?

Solution

Some of the printed values may be less than or equal to 7, and some may be greater than or equal to 7.

Problem #017

Tags: binary search, verifying recursion

Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number $x$ is the smallest integer that is $\geq x$). The full code is shown below for convenience:


import math

def new_binary_search(arr, start, stop, target):
    if stop <= start:
        return None

    middle = math.ceil((start + stop) / 2)

    if arr[middle] == target:
        return middle
    elif arr[middle] < target:
        return new_binary_search(arr, middle + 1, stop, target)
    else:
        return new_binary_search(arr, start, middle, target)

Which of the following statements about the correctness of new_binary_search is true? You may assume that arr will be a list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop = len(arr) - 1.

Solution

new_binary_search may recurse infinitely

Problem #018

Tags: best and worst case, mergesort

True or False: the best case time complexity of mergesort is $\Theta(n)$.

True False

Solution

False.

Problem #019

Tags: mergesort

Suppose mergesort is called on an array of size $n$. In total, how many calls to merge are made over all calls to mergesort?

Solution

$\Theta(n)$

Problem #020

Define the largest gap in a collection of numbers (also known as its range) to be greatest difference between two elements in the collection (in absolute value). For example, the largest gap in $\{4, 9, 5, 1, 6\}$ is 8 (between 1 and 9).

Suppose a collection of $n$ numbers is stored in a balanced binary search tree. What is the time complexity required of an efficient algorithm to calculate the largest gap in the collection? State your answer as a function of $n$ in asymptotic notation.

Solution

$\Theta(\log n)$

Problem #021

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

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

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

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

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

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

Suppose the numbers 41, 32, and 40 are inserted (in that order) into the below binary search tree. Draw where the new nodes will appear.

Solution

41 will be the right child of 33.

32 will be the right child of 31.

40 will be the left child of 41.

Problem #028

State (but do not solve) the recurrence describing the runtime of the following function.


def foo(n):
    if n < 10:
        print("Hello world.")
        return

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

    for i in range(6):
        foo(n//3)

Solution

$T(n) = 6 T(n/3) + \Theta(n)$.

Problem #029

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.

Problem #030

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

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.

Problem #032

Tags: expected time

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

Problem #033

Let $f$ and $g$ be as in the previous question. What are the tightest possible asymptotic bounds that can be placed on the product, $f \times g$?

As before, 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 #034

Define the smallest gap in a collection of numbers to be the smallest difference between two distinct elements in the collection (in absolute value). For example, the smallest gap in $\{4, 9, 1, 6\}$ is 2 (between 4 and 6).

Suppose a collection of $n$ numbers is stored in a balanced binary search tree. What is the time complexity required for an efficient algorithm to calculate the smallest gap of the numbers in the BST? State your answer as a function of $n$ in asymptotic notation.

Solution

$\Theta(n)$

Problem #035

Tags: binary search, recursion

Suppose binary_search has been called on an array arr with a target t that is not necessarily in the array, and with start and stop indices start and stop, respectively (remember, our convention is that the start index is included, while the stop index is excluded from the search). Which of the following must be true? Mark all which apply. You may assume that stop - start$\geq 1$.

Note: remember that any statement about an empty array is considered to be automatically true. Also, you cannot assume that this call to binary_search is the root call (it could be a recursive call).

Solution

The last two answers are both correct.

Problem #036

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

Tags: expected time

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

Problem #038

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.

Now you may assume that the array is sorted.

This question has two parts:

First, give the tight theoretical lower bound for the worst case time complexity of any algorithm which solves this problem:

Solution

$\Theta(\log n)$

Second, give a short description of an optimal algorithm. Your description does not need to be exact or very long (3 to 4 sentences will do). You do not need to provide pseudocode, but you can if you wish.

Solution

The maximum $m$ can be found in $\Theta(1)$ time -- it is the last element of the array. Use binary search ($\Theta(\log n)$ time) to look for $m - 10$, but modify the code so that the last-checked index is returned if $m - 10$ is not found (everything to the right of that index is at least $m - 10$). Subtract this index from $n$ to find the number of elements within 10 of the maximum.

Problem #039

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

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

Tags: binary search, recursion

Suppose binary_search is called on a sorted array of size $n$. In total, how many recursive calls to binary_search are made in the worst case?

Solution

$\Theta(\log n)$

Problem #042

Tags: verifying recursion

Consider the code below which claims to compute the maximum of the input array. Adopt the convention that the maximum of an empty array is $-\infty$.


import math
def maximum(arr, start=0, stop=None):
    """Find the maximum of arr[start:stop]."""
    if stop is None:
        stop = len(arr)
    if stop - start == 0:
        return -float('inf')

    middle = math.floor((start + stop) / 2)
    left = maximum(arr, start, middle)
    right = maximum(arr, middle, stop)
    if left > right:
        return left
    else:
        return right

Will this code always return the correct answer (the maximum)? If yes, simply say so. If no, describe what might happen (recurse infinitely, return the wrong answer, raise an index error, etc.).

Solution

This code will recurse infinitely when called on an array with a single element.

Problem #043

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.

Problem #044

Solve the below recurrence, stating the solution in asymptotic notation. Show your work.

\[ T(n) = \begin{cases} 2 T(n/4) + \Theta(n) & n > 1 \\ c & n = 1 \end{cases}\]

Solution

$\Theta(n)$.

We'll unroll several times:

\[\begin{aligned} T(n) &= 2 T(n/4) + n \\ &= 4 T(n/16) + \frac{n}{2} + n \\ &= 8 T(n/64) + \frac{n}{4} + \frac{n}{2} + n \\ \end{aligned}\]

The pattern seems to be that on the $k$th unroll:

\[ T(n) = 2^k T\left(\frac{n}{4^k}\right)+ n \left( 1 + \frac12 + \frac14 + \ldots + \frac{1}{2^{k-1}}\right)\]

The base case is reached when $k = \log_4 n$. Plugging this back in, we find:

\[ T(n) = 2^{\log_4 n} T(1) + n \left(1 + \frac12 + \frac 14 + \ldots + \frac{1}{2^{\log_4 n - 1}}\right)\]

If you reached this point, you got most of the credit. If you're unsure of what to do with $2^{\log_4 n}$, there are a couple of ways foward.

The first (and easiest) way is to realize that $2^{\log_4 n}$ is smaller than $2^{\log_2 n} = n$, so $2^{\log_4 n} = O(n)$. Similarly, we've seen the summation of $1 + 1/2 + 1/4 + \ldots$ several times -- this is a geometric sum, and converges to 2 when there are infinitely many terms. There are a finite number of terms here, so the sum is $< 2$. Altogether, we have:

\[ T(n) = O(n) T(1) + n \Theta(1) = \Theta(n) \]

The second approach is to remember log properties to simplify $2^{\log_4 n}$ to $\sqrt{n}$. This can be seen by using the ``change of base'' formula:

\[\log_b x = \frac{\log_a x}{\log_a b}. \]

In this case:

\[\log_4 n = \frac{\log_2 n}{\log_2 4} = \frac{\log_2 n}{2}\]

And therefore $2^{\log_4 n} = 2^{(\log_2 n) / 2} = \left(2^{\log_2 n}\right)^{1/2} = n^{1/2} = \sqrt n$. This shows that the first term in the recurrence is $\Theta(\sqrt n)$. The second term is still $\Theta(n)$, so the solution is $\Theta(n)$.

Problem #045

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.

Problem #046

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.

Problem #047

Tags: binary search

Consider the problem of searching for an element t in a sorted array, with the added requirement that if t is in the array multiple times, we return the index of the first occurrence. For example, if arr = [3, 4, 4, 4, 5, 8], and t = 4, the code should return 1, since the first 4 is at index one.

binary_search as implemented in lecture may not necessarily return the index of the first occurrence of t, but it can be modified so that it does.

Fill in the blanks below so that the function returns the index of the first occurence of t. Hint: last_seen should keep track of the index of the last known occurrence of t.



import math
def mbs(arr, t, start, stop, last_seen=None):
    if start - stop <= 0:
        return last_seen

    middle = math.floor((stop - start) / 2)

    if arr[middle] == t:
        # _________ <-- fill this in
    elif arr[middle] < t:
        # _________ <-- fill this in
    else:
        # _________ <-- fill this in

Solution

Here is how the blanks should be filled in:



if arr[middle] == t:
    return mbs(arr, t, start, middle, middle)
elif arr[middle] < t:
    return mbs(arr, t, middle + 1, stop, last_seen)
else:
    return mbs(arr, t, start, middle, last_seen)

If we see arr[middle] == t, we know that this is either the first occurrence of t in the array, or the first occurrence of t in the left half of the array. Therefore, we make a recursive call to mbs on the left half of the array, keeping track of middle as the index of the leftmost occurrence of t we have seen so far (this is done by passing it as the value to last_seen).

The other recursive calls are the same as in the original binary_search function, except that we pass last_seen as an argument to the recursive calls. This is because we want to keep track of the leftmost occurrence of t we have seen so far.

Eventually, we will reach a point where start - stop <= 0. At this point, we return last_seen, which is the index of the leftmost occurrence of t we have seen so far. This will necessarily be the leftmost occurrence of t in the array.

Problem #048

Tags: quickselect

True or False: quickselect requires the input array to be sorted in order to function correctly.

True False

Solution

False.

Problem #049

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

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

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

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

Tags: binary search

Consider the version of binary search shown below:



import math
def binary_search(arr, t, start, stop):
    """
    Searches arr[start:stop] for t.
    Assumes arr is sorted.
    """
    if stop - start <= 0:
        return None
    middle = math.floor((start + stop)/2)
    if arr[middle] == t:
        return middle
    elif arr[middle] > t:
        return binary_search(arr, t, start, middle)
    else:
        return binary_search(arr, t, middle+1, stop)

True or false: if the target element t occurs multiple times in the array, binary_search is guaranteed to return the first occurrence.

You may assume that arr is sorted and that binary_search(arr, t, 0, len(arr)) is called.

True False

Solution

False.

Problem #054

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

Suppose the numbers 41, 32, and 33 are inserted (in that order) into the below binary search tree. Draw where the new nodes will appear.

Solution

41 will become the left child of 46.

32 will become the left child of 35.

33 will become the right child of 32.

Problem #056

State (but do not solve) the recurrence describing the runtime of the following function.


def foo(n):
    if n < 1:
        return 0

    for i in range(n**2):
        print("here")

    foo(n/2)

Solution

$ T(n) = \begin{cases} \Theta(1), & n = 1\\ T(n/2) + \Theta(n^2)% , & n > 1 \end{cases}$

Problem #057

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.

Problem #058

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.

Problem #059

Tags: expected time

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

Problem #060

Consider again the function $f(n) = n \times( \sin(n) + 1)$ from the previous problem.

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

True False

Solution

True.

Problem #061

Define the largest gap in a collection of numbers to be the largest difference between two distinct elements in the collection (in absolute value). For example, the largest gap in $\{4, 9, 1, 6\}$ is 8 (between 1 and 9).

Suppose a collection of $n$ numbers is stored in a balanced binary search tree. What is the time complexity required for an efficient algorithm to calculate the largest gap of the numbers in the BST? State your answer as a function of $n$ in asymptotic notation.

Solution

$\Theta(\log n)$

Problem #062

Tags: binary search, loop invariants

Consider the iterative implementation of binary search shown below:


import math

def iterative_binary_search(arr, target):

    start = 0
    stop = len(arr)

    while (stop - start) > 0:
        print(arr[start])
        middle = math.floor((start + stop) / 2)
        if arr[middle] == target:
            return middle
        elif arr[middle] > target:
            stop = middle
        else:
            start = middle + 1

    return None

Which of the following loop invariants is true, assuming that arr is sorted and non-empty, and target is not in the array? Select all that apply.

After each iteration, stop - start >= 0.

After each iteration, stop - start >= 1.

After each iteration, arr[start] <= target.

Solution

The first option is correct.

Problem #063

Consider again the problem of determining whether there exists a pair of numbers in an array which, when added together, equal the maximum number in the array. Additionally, assume that the array is sorted.

True or False: $\Theta(n)$ is a tight theoretical lower bound for this problem.

True False

Solution

True.

Any algorithm must take $\Omega(n)$ time in the worst case, since in the worst case all elements of the array must be read.

This is tight because there is an algorithm that will compute the answer in worst-case $\Theta(n)$ time. Namely, this is an instance of the ``movie problem'' from lecture, where instead of finding two numbers which add to an arbitrary target, we're looking for a specific target: the maximum. We saw an algorithm that solved the movie problem in $\Theta(n)$ time, where $n$ was the number of movies. Since the maximum is computed in $\Theta(1)$ time for a sorted array, we can use the same algorithm to solve this in $\Theta(n)$ time as well.

Problem #064

Tags: expected time

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

Tags: sorted structure, theoretical lower bounds

Suppose $a$ and $b$ are two numbers, with $a \leq b$. Consider the problem of counting the number of elements in an array which are between $a$ and $b$; that is, the number of elements $x$ such that $a \leq x \leq b$. You may assume for simplicity that both $a$ and $b$ are in the array, and there are no duplicates.

Part 1)

What is a tight theoretical lower bound for this problem, assuming that the array is unsorted? State your answer in asymptotic notation as a function of the number of elements in the array, $n$.

Solution

$\Theta(n)$.

Since the array is in arbitrary order, we have to at least read all of the elements, taking $\Omega(n)$ time. This is a tight lower bound, because we can count the number of elements between $a$ and $b$ by looping through and checking whether each element is in $[a, b]$ in linear time.

Part 2)

What is a tight theoretical lower bound for this problem, assuming that the array is sorted? State your answer in asymptotic notation as a function of the number of elements in the array, $n$.

Solution

$\Theta(\log n)$.

We can do this in worst-case $\Theta(\log n)$ time with binary search: find the index of $a$ in worst-case $\Theta(\log n)$ time; find the index of $b$ in worst-case $\Theta(\log n)$ time; and subtract the two indices (and add one) to get the total number of elements between $a$ and $b$, inclusive.

There cannot be an algorithm that is better than $\Theta(\log n)$ in the worst case, so this is a tight lower bound. To see why, recognize that we can solve the query problem (determine True/False if a target $t$ is in a sorted array) with any algorithm that solves this problem by setting $a = b = t$. If an algorithm solves this problem in faster than $\Theta(\log n)$, it will also solve the query problem in faster than $\Theta(\log n)$, but we saw in class that the query problem has a theoretical lower bound of $\Theta(\log n)$, so such an algorithm cannot exist.

Problem #066

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

What is the worst case time complexity of the function in the last problem? State your answer using asymptotic notation.

Solution

$\Theta(n^2)$

Problem #068

Tags: recurrence relations, mergesort

Consider the modification of mergesort shown below, where one of the recursive calls has been replaced by an in-place version of selection_sort. Recall that selection_sort takes $\Theta(n^2)$ time.


def kinda_mergesort(arr):
    """Sort array in-place."""
    if len(arr) > 1:
        middle = math.floor(len(arr) / 2)
        left = arr[:middle]
        right = arr[middle:]
        mergesort(left)
        selection_sort(right)
        merge(left, right, arr)

What is the time complexity of kinda_mergesort?

Solution

$\Theta(n^2)$

Problem #069

Tags: recursion, verifying recursion

Consider the code below which claims to compute the most common element in the array, returning a pair: the element along with the number of times it appears.


import math

def most_common(arr, start, stop):
    """Attempts to compute the most common element in arr[start:stop]."""
    if stop - start == 1:
        return (arr[start], 1)

    middle = math.floor((start + stop) / 2)

    left_value, left_count = most_common(arr, start, middle)
    right_value, right_count = most_common(arr, middle, stop)

    if left_count > right_count:
        return (left_value, left_count)
    else:
        return (right_value, right_count)

You may assume that the function is always called on a non-empty array, and with start = 0 and stop = len(arr). Will this code always return the correct answer (the most common element)?

Solution

No: it will run without error, but the element returned may not be the most common element in the array.

It is not true in general that the most common element in the array is the most common in the left or the right. As a simple example, take: [1,1,1,0,0,2,2,2,0,0]. 1 is the most common in the left half, and 2 is the most common in the right half, but 0 is the most common overall.

So even if we assume that most_common(arr, start, middle) finds the most common element in left half of the array, and most_common(arr, middle, stop) finds the most common element in the right of the array, it is not necessarily the case that the most common between them is the overall most common in the array.

You can also quickly see that the code cannot be correct because nowhere is a count greater than one ever returned.

Problem #070

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.

Problem #071

Solve the below recurrence, stating the solution in asymptotic notation. Show your work.

\[ T(n) = \begin{cases} T(n/2) + \Theta(n) & n > 1 \\ \Theta(1) & n = 1 \end{cases}\]

Solution

$\Theta(n)$.

Unrolling several times, we find:

\[ T(n) = T(n/2) + n \\ = T(n/4) + \frac{n}{2} + n \\ = T(n/8) + \frac{n}{4} + \frac{n}{2} + n \\\]

On the $k$th unroll, we'll get:

\[ T(n) = T(n/2^k) + \left[ n + \frac{n}{2} + \frac{n}{4} + \ldots + \frac{n}{2^{k-1}}\right]\]

It will take $\log_2 n$ unrolls to each the base case. Substituting this for $k$, we get:

\[\begin{aligned} T(n) &= T(n/2^{\log_2 n}) + \left[ n + \frac{n}{2} + \frac{n}{4} + \ldots + \frac{n}{2^{(\log_2 n)-1}} \right] \\ &= T(1) + n\left[ 1 + \frac{1}{2} + \frac{1}{4} + \ldots + \frac{1}{2^{(\log_2 n)-1}} \right] & = T(1) + c n\\ & = \Theta(1) + c n\\ &= \Theta(n) \end{aligned}\]

Problem #072

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

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

Tags: binary search, loop invariants

Consider iterative_binary_search below and note the print statement in the while-loop:



import math

def iterative_binary_search(arr, target):

    start = 0
    stop = len(arr)

    while (stop - start) > 0:
        print(arr[start])
        middle = math.floor((start + stop) / 2)
        if arr[middle] == target:
            return middle
        elif arr[middle] > target:
            stop = middle
        else:
            start = middle + 1

    return None

Suppose iterative_binary_search is run on the array:


[-202, -201, -200, -50, -20, -10, -4, -3, 0, 1, 3, 5, 6, 7, 9, 10, 12, 15, 22]

with target 11.

What will be the last value of arr[start] printed?

Solution

10

Problem #075

Tags: quickselect, loop invariants

Recall the partition operation from quickselect. Which of the following arrays could have been partitioned at least once? Select all that apply.

Solution

The second, third, and last all should be selected.

Problem #076

The function below counts how many elements What is the time complexity of the following function in terms of $n$? Remember to state your answer in the simplest terms possible.


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

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

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

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

Suppose a collection of $n$ numbers is stored in a balanced binary search tree. What is the time complexity required of an efficient algorithm to calculate the mean of the collection? State your answer as a function of $n$ in asymptotic notation.

Solution

$\Theta(n)$

Problem #081

Tags: recursion, mergesort

Consider the code for mergesort and merge where a new print-statement has been added to merge:



def mergesort(arr):
    """Sort array in-place."""
    if len(arr) > 1:
        middle = math.floor(len(arr) / 2)
        left = arr[:middle]
        right = arr[middle:]
        mergesort(left)
        mergesort(right)
        merge(left, right, arr)

def merge(left, right, out):
    """Merge sorted arrays, store in out."""
    left.append(float('inf'))
    right.append(float('inf'))
    left_ix = 0
    right_ix = 0

    for ix in range(len(out)):
        print("Here!") # <---- the newly-added line
        if left[left_ix] < right[right_ix]:
            out[ix] = left[left_ix]
            left_ix += 1
        else:
            out[ix] = right[right_ix]
            right_ix += 1

Suppose mergesort is called on an array of size $n$. In total, how many times will "Here!" be printed?

Solution

$\Theta(n \log n)$

Problem #082

Solve the recurrence below, stating the solution in asymptotic notation. Show your work.

\[ T(n) = \begin{cases} 2 T(n/4) + \Theta(n),& n > 1\\ 1,& n = 1 \end{cases}\]

Solution

$\Theta(n)$

Problem #083

Tags: binary search, recursion, verifying recursion

Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number $x$ is the smallest integer that is $\geq x$). The full code is shown below for convenience:


import math

def new_binary_search(arr, start, stop, target):
    if stop <= start:
        return None

    middle = math.ceil((start + stop) / 2)

    if arr[middle] == target:
        return middle
    elif arr[middle] < target:
        return new_binary_search(arr, middle + 1, stop, target)
    else:
        return new_binary_search(arr, start, middle, target)

You may assume that arr will be a sorted list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop = len(arr).

Part 1)

True or False: there are input arrays on which new_binary_search will recurse infinitely.

True False

Solution

True.

Part 2)

True or False: there are input arrays on which new_binary_search will raise an IndexError because it attempts to access an element of the array which does not exist.

True False

Solution

True.

Problem #084

True or False: the best case time complexity of mergesort is $\Theta(n)$.

True False

Solution

False.

Problem #085

State (but do not solve) the recurrence describing the run time of the following code, assuming that the input, arr, is a list of size $n$.


def foo(arr, stop=None):
    if stop is None:
        stop = len(arr) - 1

    if stop < 0:
        return 1

    last = arr[stop]
    return last * foo(arr, stop - 1)

Solution

$T(n) = T(n-1) + \Theta(1)$

Problem #086

Tags: quickselect

True or False: in order to guarantee that its output is correct, quickselect must be called on a sorted list.

True False

Solution

False.

Problem #087

Consider the following problem: given a (possibly unsorted) list of size $n$ containing only ones and zeros, determine if the number of ones is equal to the number of zeros.

Part 1)

What is a tight theoretical lower bound for this problem? State your answer as a function of $n$ using asymptotic notation.

Solution

$\Theta(n)$

Part 2)

Now assume that the input array is guaranteed to have the following structure: there will be $a$ ones, followed by $b$ zeros, followed again by $a$ ones. An example of such an array is: [1, 1, 0, 0, 0, 1, 1]. In this example, $a = 2$ and $b = 3$.

Consider the same problem as before: that is, given an array satisfying the above assumption, determine if the number of ones in the array is equal to the number of zeros. Of course, $a$ and $b$ are not known ahead of time.

What is a tight theoretical lower bound for this problem?

Solution

$\Theta(1)$ Let $n$ be the length of the array. Assume that $n$ is even (if it is odd, we can immediately say that there are not an equal number of ones and zeros). In fact, we can assume that $n$ is divisible by four, since $n = a + b + a = 2a + b$, which must equal $4a$ if there are an equal number of ones and zeros.

For there to be an equal number of ones as zeros, the middle $n/2$ elements must be zero, while the first $n/4$ and last $n/4$ must be ones. If that is the case, then the last one in the first group of ones will occur at index $n / 4 - 1$, and the first zero will occur at $n / 4 $ A constant-time algorithm is to check the element at index $n/4 - 1$ and verify that it is a one. Then we check the element at index $n/4 $ and check that it is a zero.

Consider, for example, this array with $n = 10$:

\[\mintinline{python}{[1, 1, 1, 0, 0, 0, 0, 1, 1, 1]}\]

Then $n / 10 = 10 / 4 = 2.5 = 2$. Therefore, we check the elements at index 1 and 2 in constant time and find them to both be one, which tells us that this array does not have an equal number of zeros and ones.

Now consider the array below:

\[\mintinline{python}{[1, 1, 0, 0, 0, 0, 1, 1]}\]

Since $n = 8$, we again check the elements at index 1 and 2. We find 1 and 0, which tells us that the array does have an equal number of zeros and ones, as expected.

Problem #088

Tags: expected time

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

Problem #089

Tags: expected time

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

Problem #090

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

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.

Problem #092

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

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.

Problem #094