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

```python
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)$