Chapter 2: Runtime Analysis and Asymptotic Analysis

[Ch 2] Code modeling

Expressing the number of operations a piece of code performs as a function f(n) of the input size.

[Ch 2] Code modeling: what are the counting rules?

Each basic operation (assignment, arithmetic, comparison) counts as 1. A loop multiplies its body's cost by the number of iterations.

[Ch 2] Asymptotic analysis

Reducing f(n) to a complexity class by keeping the dominant term and dropping lower-order terms and coefficients.

[Ch 2] Big-O (O)

Upper bound: f(n) grows no faster than the given function.

[Ch 2] Big-Omega (Ω)

Lower bound: f(n) grows at least as fast as the given function.

[Ch 2] Big-Theta (Θ)

Tight bound: f(n) is both O and Ω of the same function.

[Ch 2] Case analysis

Analyzing an algorithm's best, worst, and average case, which depend on how the input is arranged.

[Ch 2] Simplify f(n) = 6n + 3.

O(n), linear time. Drop the constant 3 and the coefficient 6.

[Ch 2] Simplify f(n) = 3n² + 5n + 100.

O(n²). The n² term dominates, so drop 5n, 100, and the coefficient 3.

[Ch 2] Simplify f(n) = 4n log n + 2n.

O(n log n). The n log n term dominates n.

[Ch 2] Code-modeling example: how many operations per loop iteration, and what is f(n)?

7 per iteration (1 check + 2 + 2 + 2), so f(n) = 7n + 3, which is O(n). The original notes said 6n + 3.

[Ch 2] Runtime of two nested loops that each run n times?

O(n²)

[Ch 2] Code: write the full code-modeling example (with operation counts).

```python
total = 0 # 1 op (assignment)
i = 0 # 1 op (assignment)
while i < n: # 1 op per check: n passing checks + 1 final failed check
product = i * 3 # 2 ops (multiplication, assignment)
total = total + product # 2 ops (addition, assignment)
i = i + 1 # 2 ops (addition, assignment)
```

[Ch 2] Code-modeling example: where does the "+3" in f(n) come from?

Two assignments before the loop (`total = 0`, `i = 0`), plus the final condition check that fails and ends the lo