Performance Scaling

Before formal definitions, let's build intuition. Suppose you have an algorithm
that takes $n$ seconds on input of size $n$. You scale the input by a factor
of 10 — what happens?

The lesson. A linear-time algorithm on $n = 1000$ is 10× slower than on
$n = 100$. A quadratic one is 100× slower. An exponential one becomes
impossible.

Practical examples:
- Looking up a name in a sorted list (binary search): logarithmic.
- Sorting $n$ items: $O(n \log n)$ — near-linear.
- Checking all pairs in a list: quadratic.
- Solving a traveling salesman by brute force: factorial.

The "one year" example. Suppose algorithm A does $n$ operations,
algorithm B does $100n$ operations. On a machine doing $10^7$ ops/sec, B is
100× slower than A. If A takes 5 minutes, B takes 500 minutes — about 8
hours. If C does $7n^2$ operations, on $n = 1000$ it does $7 \times 10^6$
ops — fine. On $n = 10^6$ it does $7 \times 10^{12}$ — about 8 days.

The growth class matters far more than constants. We capture this formally
with Landau sets next.