Homework: Big O and Algorithm Analysis

Homework: Big O and Algorithm Analysis#

Instructions: Please answer the following questions on paper. Show your work and explain your reasoning clearly.

Part 1: Counting Steps#

Consider the following Python function, which checks if a list contains any duplicate values. Assume the input list L has n elements.

def has_duplicate(L):
  for i in range(len(L)):         # Outer loop
    for j in range(i + 1, len(L)):  # Inner loop
      if L[i] == L[j]:            # Comparison
        return True               # Return if duplicate found
  return False                    # Return if no duplicates

  1. Worst-Case Analysis:

    • What is the worst-case scenario for this algorithm in terms of runtime? (i.e., what kind of input list would make it take the longest?)

    • Following the step-counting method from the notes, write a function \(T(n)\) that represents the total number of steps taken in the worst case. You can count assignments, comparisons, and returns as basic steps.

  2. Best-Case Analysis:

    • What is the best-case scenario for this algorithm?

    • How many steps does the algorithm take in the best case? Is it dependent on n?

Part 2: Comparing Function Growth#

For each pair of functions below, determine which function dominates the other for large n. Assuming that \(c=1\), find a “crossover point” \(n_0\) such that for all \(n \ge n_0\), the dominant function is greater than the other.

  1. \(f(n) = 8n + 100\) vs. \(g(n) = 2n^2\)

  2. \(f(n) = 10n \log_2(n)\) vs. \(g(n) = \frac{1}{2}n^2\)

  3. \(f(n) = 2^n\) vs. \(g(n) = n^4\)

Part 3: Big O Classification#

For each of the following functions, determine the tightest possible Big O classification from the main “buckets” (\(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n \log n)\), \(O(n^2)\), \(O(n^3)\), \(O(2^n)\)). Justify your answer by finding constants c and n_0 that satisfy the formal definition of Big O: \(f(n) \in O(g(n))\) if there exist a \(c\) and \(n_0\) so that \(f(n) \le c \cdot g(n)\) for all \(n \ge n_0\).

  1. \(f(n) = 50n^2 + 200n + 1000\)

  2. \(f(n) = \frac{n(n-1)}{2}\)

  3. \(f(n) = 75 \log_2(n) + 5n + 2\)

  4. \(f(n) = 10^6\)

Part 4: Conceptual Questions#

  1. Explain in your own words why we ignore constant factors and lower-order terms when determining an algorithm’s Big O complexity.

  2. An algorithm takes 5 seconds to run on an input of size n=100. How long would you estimate it would take to run on an input of size n=200 if the algorithm’s time complexity is:

    • a) \(O(n)\)

    • b) \(O(n^2)\)

    • c) \(O(2^n)\)