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