Solution Key: Big O and Algorithm Analysis

Solution Key: Big O and Algorithm Analysis#

Part 1: Counting Steps#

1. Worst-Case Analysis:

  • What is the worst-case scenario?

    • The “worst-case” is the input that forces the algorithm to do the most possible work. For the has_duplicate function, the goal is to find a matching pair of elements. The algorithm stops as soon as it finds one. Therefore, the longest possible runtime occurs when the algorithm never finds a duplicate, because it is forced to check every single possible pair of elements before it can conclude that no duplicates exist. For example, [10, 20, 30, 40].

  • Step Counting Function \(T(n)\): Let’s analyze the work done for a list of size n. The main work happens in the comparison if L[i] == L[j]:, which is nested inside two loops. To find the total steps, we need to count how many times that comparison runs.

    Let’s trace for a small list, n=4. i will go from 0 to 3.

    • When i = 0, the inner loop j goes from 1 to 3 (3 iterations). Comparisons: L[0]==L[1], L[0]==L[2], L[0]==L[3].

    • When i = 1, the inner loop j goes from 2 to 3 (2 iterations). Comparisons: L[1]==L[2], L[1]==L[3].

    • When i = 2, the inner loop j goes from 3 to 3 (1 iteration). Comparison: L[2]==L[3].

    • When i = 3, the inner loop range(4, 4) is empty (0 iterations).

    The total number of comparisons is \(3 + 2 + 1 = 6\).

    Generalizing this pattern for a list of size n, the number of comparisons is:

    \[(n-1) + (n-2) + (n-3) + \dots + 2 + 1\]

    As shown in the course notes, this sum has a well-known formula:

    \[\sum_{i=1}^{n-1} i = \frac{(n-1)n}{2}\]

    If we define our total step function \(T(n)\) as being primarily driven by this dominant operation (the comparisons), we get:

    \[T(n) = \frac{n(n-1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n\]

    This function shows that the number of steps grows quadratically with the input size n.

2. Best-Case Analysis:

  • What is the best-case scenario? The “best-case” is the input that allows the algorithm to finish its job in the least amount of time. For this function, that means finding a duplicate on the very first try. For example, [5, 5, 12, 15].

  • How many steps does it take? In this scenario, the code executes as follows:

    1. The outer loop starts with i = 0.

    2. The inner loop starts with j = 1.

    3. The very first comparison, if L[0] == L[1]:, is true.

    4. The function immediately executes return True and stops.

    The algorithm performs only a handful of steps (a few loop initializations, one comparison, one return). The crucial insight is that this number of steps is constant. It doesn’t matter if the list has 10 elements or 10 million; if the first two are duplicates, the work done is the same. Therefore, the number of steps is not dependent on n.

Part 2: Comparing Function Growth#

This section is about determining which of two functions will grow faster as n gets very large. The function that grows faster is said to “eventually dominate” the other. We are looking for the “crossover point” (\(n_0\)), which is the value of n after which the dominant function is always larger. We can find this via algebra, plotting the functions, or trying values.

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

    • Dominant Function: \(g(n) = 2n^2\) is a quadratic function (\(O(n^2)\)), while \(f(n) = 8n + 100\) is a linear function (\(O(n)\)). Quadratic functions always grow faster than linear functions for large n. Therefore, \(g(n)\) eventually dominates.

    • Crossover Point: We need to find the n where \(2n^2\) becomes permanently greater than \(8n + 100\).

      • n=9: \(g(9) = 2(81) = 162\). \(f(9) = 8(9) + 100 = 72 + 100 = 172\). (\(f(n)\) is bigger).

      • n=10: \(g(10) = 2(100) = 200\). \(f(10) = 8(10) + 100 = 80 + 100 = 180\). (\(g(n)\) is bigger).

      • From this point on, \(g(n)\) will continue to be larger. The crossover point is \(n_0 = 10\).

import plotly.graph_objects as go
import numpy as np

n = np.arange(0, 21)
f_n = 8 * n + 100
g_n = 2 * n**2

fig = go.Figure()
fig.add_trace(go.Scatter(x=n, y=f_n, mode='lines+markers', name='f(n) = 8n + 100'))
fig.add_trace(go.Scatter(x=n, y=g_n, mode='lines+markers', name='g(n) = 2n^2'))

fig.show()

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

    • Dominant Function: \(g(n) = \frac{1}{2}n^2\) is quadratic (\(O(n^2)\)), while \(f(n)\) is n-log-n (\(O(n \log n)\)). Quadratic functions grow faster than n-log-n functions. Therefore, \(g(n)\) eventually dominates.

    • Crossover Point: We need to find the n where \(\frac{1}{2}n^2 > 10n \log_2(n)\). We can simplify by dividing by n: \(\frac{1}{2}n > 10 \log_2(n)\), or \(n > 20 \log_2(n)\). Let’s find this with a plot.

n = np.arange(1, 200)

f_n = 10 * n * np.log2(n)
g_n = 0.5 * n**2

fig = go.Figure()

fig.add_trace(go.Scatter(x=n, y=f_n,
                    mode='lines+markers',
                    name='$f(n) = 10n \\log_2(n)$'))
fig.add_trace(go.Scatter(x=n, y=g_n,
                    mode='lines+markers',
                    name='$g(n) = 0.5n^2$'))


fig.show()

Looks like 144.

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

Dominant Function: \(f(n) = 2^n\) is an exponential function (\(O(2^n)\)), while \(g(n) = n^4\) is a polynomial function (\(O(n^k)\)). Exponential functions grow dramatically faster than any polynomial function. Therefore, \(f(n)\) eventually dominates \(g(n)\).

Crossover Point: We test values to find where \(2^n > n^4\).

  • n=16: \(2^{16} = 65,536\). \(16^4 = (2^4)^4 = 2^{16} = 65,536\). (They are equal).

  • n=17: \(2^{17} = 131,072\). \(17^4 = 83,521\). (\(f(n)\) is now bigger).

  • The crossover point is \(n_0 = 17\).

n = np.arange(1, 21)
f_n = 2 ** n
g_n = n ** 4

fig = go.Figure()

fig.add_trace(go.Scatter(x=n, y=f_n,
                    mode='lines+markers',
                    name='$f(n) = 2^n$'))
fig.add_trace(go.Scatter(x=n, y=g_n,
                    mode='lines+markers',
                    name='$g(n) = n^4$'))
fig.show()

Part 3: Big O Classification#

Big O notation is a way to categorize algorithms by their dominant growth rate. We simplify a function to its “tightest possible” classification, ignoring constant multipliers and lower-order terms because they become insignificant for large n. The formal definition is that \(f(n) \in O(g(n))\) if we can find constants \(c\) and \(n_0\) such that \(f(n) \leq c \cdot g(n)\) for all \(n \geq n_0\). There are many, many correct answers to these questions.

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

    • Big O: The dominant term (the one that grows fastest) is \(50n^2\). The growth rate family is \(n^2\), so the classification is \(O(n^2)\).

    • Justification: We want to show that \(50n^2 + 200n + 1000 \le c \cdot n^2\). I choose a \(c\) of 51. \(51n^2\) eventually dominates \(f(n)\) starting at \(n_0=205\).

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

    • Big O: If we expand the function, we get \(f(n) = \frac{1}{2}n^2 - \frac{1}{2}n\). The dominant term is \(\frac{1}{2}n^2\). This falls into the \(O(n^2)\) bucket.

    • Justification: We want to show \(\frac{1}{2}n^2 - \frac{1}{2}n \le c \cdot n^2\). I choose a \(c\) of 1. \(n^2\) eventually dominates \(f(n)\) starting at \(n_0=0\).

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

    • Big O: Comparing the terms, the linear term 5n grows faster than the logarithmic term 75 log(n) and the constant 2. So, the classification is \(O(n)\).

    • Justification: We want to show \(75 \log_2(n) + 5n + 2 \le c \cdot n\). I choose \(c=6\). \(6n\) eventually dominates \(f(n)\) starting at \(n_0=713\).

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

    • Big O: The value of this function is a large number, but it is constant. It does not change as n changes. Therefore, its classification is \(O(1)\).

    • Justification: We want to show \(10^6 \le c \cdot 1\). I choose \(c=10^6+1\). \(10^6+1>f(n)\) for all \(n\), starting at \(n_0=0\).

Part 4: Conceptual Questions#

  1. Why do we ignore constant factors and lower-order terms? Imagine you’re planning a cross-country flight. The total time is dominated by the hours spent in the air. The 15 minutes it takes to taxi on the runway (a lower-order term) and whether the plane flies at 550 mph or 560 mph (a constant factor difference) are insignificant to the overall estimate. Similarly, in algorithm analysis, we focus on how the runtime behaves as the input n gets huge. For a massive n, the term with the highest power (e.g., \(n^2\)) grows so much faster than lower-order terms (like n) that the lower-order terms contribute almost nothing to the final result. Additionally, the growth term is much more impactful in defining how much work is done for large \(n\) than any coefficient. Big O is about capturing this high-level scaling behavior, so we simplify by ignoring the less impactful parts.

  2. Runtime Estimation:

    • a) \(O(n)\): The runtime is linearly proportional to the input size. If you double the input n, you double the runtime.

      • Estimated time: \(5s \times \frac{200}{100} = 5s \times 2 = \textbf{10 seconds}\).

    • b) \(O(n^2)\): The runtime is proportional to the square of the input size. If you double the input n, you multiply the runtime by \(2^2 = 4\).

      • Estimated time: \(5s \times (\frac{200}{100})^2 = 5s \times 4 = \textbf{20 seconds}\).

    • c) \(O(2^n)\): The runtime grows exponentially. The relationship is \(T(n) \approx c \cdot 2^n\).

      • The ratio of runtimes is \(\frac{T(200)}{T(100)} \approx \frac{c \cdot 2^{200}}{c \cdot 2^{100}} = 2^{100}\).

      • Estimated time: \(5s \times 2^{100}\). This is an unimaginably huge number, highlighting that exponential algorithms are not practical for large inputs.