Runtime Questions

Runtime and Big-O Notation Questions

Conceptual

  1. True or False: A function with a big-O notation of O(n) will always run faster than a function with a big-O notation of O(n2) for all inputs.
SOLUTION This is False. A function with big-O notation of O(n) will theoretically run faster than a function with a big-O notation of O(n2) on a worst case input.

  1. What type of input does Big-O notation consider?

    1. Best Case

    2. Worst Case

    3. Average Case

SOLUTION Worst Case.
  1. True or False: Big-O notation provides a precise measurement of the actual runtime of an algorithm on a specific machine.
SOLUTION False.

  1. If an algorithm has a time complexity of O(1), it means its runtime is:

    1. Linear

    2. Constant

    3. Quadratic

    4. Exponential

SOLUTION Constant

  1. If an algorithm has a time complexity of O(n), it means its runtime is:

    1. Linear

    2. Constant

    3. Quadratic

    4. Exponential

SOLUTION Linear

  1. If an algorithm has a time complexity of O(n2), it means its runtime is:

    1. Linear

    2. Constant

    3. Quadratic

    4. Exponential

SOLUTION Quadratic

  1. If an algorithm has a time complexity of O(2n), it means its runtime is:

    1. Linear

    2. Constant

    3. Quadratic

    4. Exponential

SOLUTION Exponential
  1. Insertion sort has a big-O runtime of:
SOLUTION O(n2)
  1. Selection sort has a big-O runtime of:
SOLUTION O(n2)

  1. Consider the following function: py def foo(outer_input: list[str], inner_input: list[str]) -> None: """Nested loop!""" for x in outer_input: for y in inner_input: print(f"{x} and {y}!") return None

    10.1. Assuming outer_input and inner_input both have length n, what is the big-O runtime of the function foo?

    10.2. If outer_input has length n2 and inner_input has length n, what would be the big-O runtime of the function foo?

    SOLUTION

    10.1. O(n2)

    10.2. O(n3)

  2. Which of the following is true about algorithms?

    1. The result of an algorithm is only affected by its inputs.

    2. An algorithm can have side effects which affect its environment.

    3. An algorithm can take an infinite number of steps to complete.

    4. The only effect that an algorithm can have is on its result.

SOLUTION The answer is b, since algorithms are a finite series of steps (eliminating c) and can be affected by and have an effect on their environment (eliminating a and d, and showing that b is true).
  1. Consider the following code snippets:
unc_pid_range: dict[int, bool] = {730000000: False, 730000001: False, ..., 730999999: False}
prime_numbers: list[int] = [2, 3, 5, 7, ..., 1000000007]

for pid in unc_pid_range:
    if pid in prime_numbers:
        unc_pid_range[pid] = True
        print(f"Prime PID found: {pid}!")
unc_pid_range: list[int] = [730000000, 730000001, ..., 730999999]
prime_numbers: dict[int, bool] = {2: False, 3: False, 5: False, 7: False, ..., 1000000007: False}

for pid in unc_pid_range:
    if pid in prime_numbers:
        prime_numbers[pid] = True
        print(f"Prime PID found: {pid}!")

Let n be the size of the unc_pid_range and let m be the size of both the prime_numbers in both code snippets. What are the runtimes of the two code snippets in big-O notation in terms of m and n? Which would you choose to use if you cared the most about speed?

SOLUTION

The first code snippet runs in time O(m ⋅ n) and the second runs in time O(n). This is because the lookup time (the in operator) takes constant time on a dictionary and linear time on a list, so in the first snippet you do an O(m) operation n times so $O(m n), but in the second you do an O(1) operation n times so O(n). Thus if you care about speed the most you would use the second method.
Contributor(s): Alyssa Lytle, Benjamin Eldridge