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 $⟨a_1,a_2,\dots ,a_n⟩$, output a permutation $⟨a_1^{\prime },\dots ,a_n^{\prime }⟩$ of it with $a_1^{\prime }\le a_2^{\prime }\le \cdots \le a_n^{\prime }$.
• An instance is one specific input that satisfies the problem's constraints. $⟨31,41,59,26,41,58⟩$ is an instance of the sorting problem; its solution is $⟨26,31,41,41,58,59⟩$.
• 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 $50n\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},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.