What an algorithm is, and why efficiency matters

The vocabulary the whole course stands on

An algorithm is a well-defined computational procedure that takes some input and produces some output in a finite amount of time. Equivalently: a finite sequence of unambiguous steps that transforms input into output. The phrase *finite time* is doing real work — it is what separates an algorithm from an arbitrary process that might loop forever.

Three words get confused constantly; pin them down now because the exam tests the distinction:

- A problem states *what* must be computed — the desired input/output relationship, in general terms. Example, the sorting problem: given a sequence $\langle a_1, a_2, \dots, a_n \rangle$, output a permutation $\langle a'_1, \dots, a'_n \rangle$ of it with $a'_1 \le a'_2 \le \dots \le a'_n$. - An instance is one specific input that satisfies the problem's constraints. $\langle 31, 41, 59, 26, 41, 58 \rangle$ is an *instance* of the sorting problem; its solution is $\langle 26, 31, 41, 41, 58, 59 \rangle$. - An algorithm is *how* — one concrete procedure that solves the problem for every instance. Many algorithms solve the same problem, which is exactly why efficiency comparisons matter.

Notice the sorting output must be a permutation of the input (you may not invent or drop values), and $\le$ (not $<$) is what permits duplicates.

What makes an algorithm *correct*

An algorithm is correct if, for every problem instance, it (1) halts in finite time, and (2) outputs the right answer. Both halves are required. An algorithm that always returns the right answer but sometimes loops forever is *not* correct; neither is one that always halts but sometimes lies.

Correctness comes *before* efficiency in the logical order: running-time analysis only means something for an algorithm that actually solves the problem. A beautiful $\Theta(\lg n)$ procedure that returns wrong answers is not a fast algorithm — it is not an algorithm *for that problem* at all. (There is a useful exception: some incorrect algorithms are still valuable when their error rate is controllable — randomized primality tests, in Module 8, are the classic case.)

Why efficiency: a better growth rate beats faster hardware

Two algorithms for the same problem can grow at very different rates. Insertion sort takes time roughly $c_1 n^2$; merge sort takes roughly $c_2 n \lg n$ (here $\lg n = \log_2 n$). The constants $c_1, c_2$ depend on the machine and the code, but the functional form — $n^2$ versus $n \lg n$ — is what dominates as $n$ grows. Because $n / \lg n \to \infty$, there is always a crossover beyond which merge sort wins, *no matter how much smaller $c_1$ is than $c_2$.*

Worked example — Computer A vs Computer B (the most-cited example in CLRS). Stack the deck for insertion sort:

- Computer A: $10^{10}$ instructions/sec, hand-optimized insertion sort needing $2n^2$ instructions. - Computer B: only $10^{7}$ instructions/sec (1000× slower hardware), merge sort from a sloppy compiler needing $50\, n \lg n$ instructions (a 25× *larger* constant).

Sort $n = 10^7$ numbers:

$$A = \frac{2 (10^7)^2}{10^{10}} = 20{,}000\text{ s} \approx 5.5\text{ hours}, \qquad B = \frac{50 \cdot 10^7 \cdot \lg(10^7)}{10^{7}} \approx 1163\text{ s} < 20\text{ minutes}.$$

Computer B finishes about 17× faster — despite slower hardware, a worse compiler, and a bigger constant. At $n = 10^8$ the gap explodes: insertion sort takes more than 23 days, merge sort under 4 hours. The lesson CLRS draws: *algorithms are a technology.* A better algorithm can overwhelm a 1000× hardware advantage, and that leverage *grows* with the problem size.

The one caveat: this only applies where a better algorithm *exists*. For the NP-complete problems in Module 9, no efficient algorithm is known — algorithmic cleverness has a boundary, and recognizing it tells you when to stop searching and reach for approximation (Module 10) instead.