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

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)

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)

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!')

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

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

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?

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?

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!")

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)

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)

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

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

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

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

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

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?

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.

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

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

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.

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)

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

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

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

Let \(f\) be the piecewise function defined as:

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

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

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.

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)

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})\).

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)

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

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)

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

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.

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

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?

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)

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:

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.

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)

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?

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?

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

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

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

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.

Let

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

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

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)

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

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)

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

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

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)

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.

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

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.

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)

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

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

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)

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

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

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.

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.

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.

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)

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.

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)

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

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?

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

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

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

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?

Let

Write \(f\) in asymptotic notation in as simplest terms possible.

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?

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

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)

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!')

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

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)

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.

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?

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

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

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

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)

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

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.

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)

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!")

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)

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

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

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

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

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)

boo(202)

\(\Theta(n^3)\) Show Answer

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)

boo(100)

\(\Theta(\log n)\) Show Answer

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


print(boo([1, 6, 6, 4, 6], [6, 7, 8, 9, 10]))

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)

\(\Theta(n^2)\) Show Answer

Professor Billy claims to have invented a new sorting algorithm: mediansort. The algorithm supposedly works by finding a median number, swapping it into the middle of the list, and recursing on the left half and the right half. Professor Billy's code is written below:

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)


def find_median(arr, start, stop):
    """Finds the index of a median of the elements in arr[start:stop]."""
    numbers = arr[start:stop]
    median = sorted(numbers)[len(numbers) // 2]
    for i in range(start, stop):
        if arr[i] == median:
            return i


import random
s = random.randint(10, 100)
arr = [random.randint(0, 1000) for _ in range(s)]
mediansort(arr, 0, len(arr))
print(arr)

The code is supposed to sort ``in place'' by modifying the input array. You may assume that find_median correctly returns the index of the median element in arr[start:stop].

Does Professor Billy's mediansort algorithm work? You may assume that it is called with start = 0 and stop = len(arr).

Consider the version of binary search shown below. This is the same as the code given in lecture, except that a single print statement has been added. This print statement prints the value of stop at the beginning of each call to binary_search.

import math
def binary_search(arr, t, start, stop):
    """
    Searches arr[start:stop] for t.
    Assumes arr is sorted.
    """
    print(stop) # <-- added print statement
    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)

Suppose binary_search is called on a sorted list with start = 0 and stop = len(n). True or False: the numbers printed must be a non-increasing sequence. That is, if \(x\) is printed before \(y\), then it must be the case that \(x \geq y\).

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

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

Consider again the function \(f(n) = \sin(12n) \cdot\cos(n) + 2\) from the previous problem.

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

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

Solution

\(\Theta(n)\).

Unrolling several times, we find:

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:

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?

\(\Theta(n \log n)\) Show Answer

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!")

boo(100)

\(\Theta(n \log n)\) Show Answer

Solution

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:

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

def boo(n):
    if n <= 1:
        return

    for i in range(3):
        boo(n/4)

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

\( T(n) = \begin{cases} \Theta(1), & n = 1\\ & n > 1 \end{cases}\)

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)

\(\Theta(n)\) Show Answer

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)

boo(100)

\(\Theta(n^4 \log n)\) Show Answer

Consider the following problem: given two sorted lists, A and B, each containing \(n\) numbers, determine if the two lists share an element in common. That is, determine if there is a number \(x\) which appears in both lists.

Draw the binary search tree that results from inserting the following nodes into an initially empty tree, in the order given: 5, 3, 1, 8, 4, 2, 6.

Solution

The code for quickselect is shown below. It is the same as the code provided in lecture, except that it contains an added print statement.

import random 
def quickselect(arr, k, start, stop):
    """Finds kth order statistic in numbers[start:stop])"""
    print("hello world!") # <--- here is the print
    pivot_ix = random.randrange(start, stop)
    pivot_ix = partition(arr, start, stop, pivot_ix)
    pivot_order = pivot_ix + 1
    if pivot_order == k:
        return arr[pivot_ix]
    elif pivot_order < k:
        return quickselect(arr, k, pivot_ix + 1, stop)
    else:
        return quickselect(arr, k, start, pivot_ix)

Suppose quickselect(arr, 3, 0, 10) is called with arr = [5, 2, 8, 3, 1, 6, 9, 7, 4, 0].

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) \}) \)

Suppose again 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)\):

\(O(\) \(n\) Show Answer \()\)

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?

\(\Theta(n^2)\) Show Answer

Let

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

\(f(n) = \Theta(\) \(\sqrt n \log n\) Show Answer )

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\)?

\(\Theta(\log n)\) Show Answer

What is the time complexity of the following function in terms of \(n\)? State your answer using asymptotic notation (e.g., \(\Theta(n)\)) in the simplest terms possible.

def foo(n):
    for i in range(n):
        for j in range(2023):
            for k in range(n - i):
                print("DSC40B")

\(\Theta(n^2)\) Show Answer

Suppose numbers is a list of integers of length \(n\). What is the time complexity of the following function in terms of \(n\)? State your answer using asymptotic notation (e.g., \(\Theta(n)\)) in the simplest terms possible.

def foo(numbers):
    for x in numbers:
        r = max(numbers) * min(numbers) * x
        print(r)

\(\Theta(n^2)\) Show Answer

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.

\(\Theta(n)\) Show Answer

What is the time complexity of the following function in terms of \(n\)? State your answer using asymptotic notation (e.g., \(\Theta(n)\)) in the simplest terms possible.

def foo(n):
    i = 1
    while i < n**3:
        i = i * 2
        for j in range(n):
            print(i + j)

\(\Theta(n\log n)\) Show Answer

Below is the merge function from the mergesort algorithm, with an added print statement:

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

    for ix in range(len(out)):
        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 this version of merge is used in mergesort, and mergesort is called on the following list:

[6, 2, 7, 1, 9, 3, 8, 5].

If all of the numbers that are printed are added up, what will the sum be?

24 Show Answer

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.

\(\Theta(n)\) Show Answer

Suppose again 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)\):

\(O(\) \(n^2\) Show Answer \()\)

Consider this code which partitions a list in a special way:

def is_even(i):
    """Returns True if i is even, False otherwise."""
    return i % 2 == 0

def mystery_partition(numbers):
    def swap(i, j):
        numbers[i], numbers[j] = numbers[j], numbers[i]

    barrier_ix = 0
    for i in range(len(numbers)):
        if is_even(numbers[i]):
            swap(i, barrier_ix)
            if numbers[barrier_ix] > numbers[0]:
                swap(0, barrier_ix)
            barrier_ix += 1


lst = [1, 5, 3, 7, 2, 4, 8, 5, 9, 6, 100]
mystery_partition(lst)
print(lst)

Which of the following loop invariants are true for this code? Select all that apply.

Note: any statement about an empty set or list is considered to be automatically true.

A rotated sorted array is an array that is the result of taking a sorted array and moving a contiguous section from the front of the array to the back of the array. For example, the array [5, 6, 7, 1, 2, 3, 4] is a rotated sorted array: it is the result of taking the sorted array [1, 2, 3, 4, 5, 6, 7] and moving the first 4 elements, [1, 2, 3, 4], to the back of the array. Sorted arrays are also rotated sorted arrays, technically speaking, since you can think of a sorted array as the result of taking the sorted array and moving the first 0 elements to the back.

The function below attempts to find the value of the minimum element in a rotated sorted array. It is given the array arr and the indices start and stop which indicate the range of the array that should be searched. One line in the function has been left blank.

import math
def find_minimum_in_rotated_sorted(arr, start, stop):
    """
    Searches arr[start:stop] for the smallest element.
    Assumes arr is a rotated sorted array.
    """
    if stop < start:
        return arr[0]
    if stop == start:
        return arr[start]
    mid = (start + stop) // 2

    if ________________:
        return arr[mid + 1]
    if arr[start] < arr[mid]:
        return find_minimum_in_rotated_sorted(arr, mid, stop)
    else:
        return find_minimum_in_rotated_sorted(arr, start, mid - 1)

What should be filled in the blank line to make this function work correctly?

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

Consider the following function which attempts to compute the maximum of a list of numbers.

import math
def maximum(numbers):
    n = len(numbers)
    if n == 0:
        return 0
    middle = math.floor(n / 2)
    return (
        maximum(numbers[:middle])
        +
        maximum(numbers[middle:])
    )

Is this code guaranteed to work for all non-empty lists?

You should adopt the convention that the maximum of an empty list is \(-\infty\).

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!")

\(\Theta(n^2)\) . Show Answer

Solve the below recurrence, stating the solution in asymptotic notation. You do not need to show your work (and your work won't be graded for partial credit, so be careful!).

\(\Theta(n)\) Show Answer

Solution

\(\Theta(n)\).

Unrolling several times, we find:

On the \(k\)th unroll, we'll get:

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

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

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

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

    foo(n // 2)

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

    foo(n // 2)

\(\Theta(n \log n)\) Show Answer

What is the time complexity of the following function in terms of \(n\)? State your answer using asymptotic notation (e.g., \(\Theta(n)\)) in the simplest terms possible.

import math
def foo(n):
    for i in range(3 * n**3 + 5 * n * math.ceil(math.log(n))):
        for j in range(math.floor(math.sqrt(n))):
            print(i + j)
        for k in range(n**2):
            print(k * i)

\(\Theta(n^5)\) Show Answer

In this problem, assume that \(A\) and \(B\) are sorted lists, each containing \(n\) numbers.

\(\Theta(1)\) Show Answer

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

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?

\(\Theta(n^2)\) Show Answer

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?

\(\Theta(n^3)\) Show Answer

Consider the function defined below:

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