The Algorithm

The exact recipe

What, after all, is an algorithm? In essence it is a flawless recipe: a finite succession of clear steps, free of any trace of ambiguity, which takes some input data, works on them methodically and always produces a correct answer, stopping with a guarantee after a reasonable number of operations. Every single step must be so elementary that whoever carries it out can do so mechanically, without asking for further explanation and without needing a scrap of intuition.

This demand for absolute precision is far sterner than it looks at first. In an ordinary cookery book, an instruction such as “stir until the mixture binds” or “brown over a moderate heat” is perfectly useful to a human cook, who can see the consistency of the sauce and smell the oven. But for a computer such a command is unintelligible: it has no senses, no experience of life and cannot guess what we meant. A step of a genuine algorithm looks rather more like: “add the number in box A to the number in box B and put the result in box C”. The processor we built in the previous lessons cannot ask questions; everything we ask of it must therefore be described without remainder, down to the last comma.

The name “algorithm” is a historical tribute to the great Persian scholar Muhammad ibn Musa al-Khwarizmi, who lived in Baghdad around the year 825. His treatise on methodical calculation with Indian numerals was translated into Latin in the Middle Ages, and the author’s name, clumsily pronounced in Europe, gave us the word “algorithm”, while another term from the title of his book — al-jabr — gave rise to the word “algebra”.

Selection sort

To see an algorithm in the flesh, let us take a classical problem: we have a heap of jumbled numbers and want to set them in increasing order. Here is a simple, intuitive recipe in three steps: go through what is left of the row and find the smallest number; swap it with the number in the first free position; repeat the same procedure starting from the next position. This method is called selection sort.

Why is this a genuine algorithm? For three fundamental reasons: first, it always ends, because at every step the unsorted zone shrinks by exactly one element; second, it gives the correct result with a guarantee for absolutely any row of numbers, however chaotically it was shuffled; third, we can work out with mathematical precision, before running the program, how many steps the machine will have to take.

How many steps

Let us count the effort: if we have n numbers, in the first round we compare the first element with the other n−1 numbers. In the second round we search among the n−2 that remain, and so on, until we reach the last. Added up, the total number of comparisons is given by the formula n·(n−1)/2 — that is, roughly half the square of n. With 10 numbers we make some 45 comparisons; with 1,000 numbers we make nearly half a million; and with a million numbers we reach the dizzying figure of 500 billion operations. That effort does not depend on luck: even if the row is already in order, the algorithm will blindly make exactly the same number of checks.

But can we be cleverer? Certainly. Think of the principle of “divide and conquer”: instead of searching through the whole heap, we split the row into two equal halves, sort each half separately and at the end weave them together (merge them), running through both in parallel, from left to right, comparing only the elements at the top. This is merge sort (Merge Sort). Here we meet again the magical binary halving from the first lesson: a row of n elements can be halved at most log₂n times, and at each level of splitting the work of weaving is proportional to n. The total volume of work falls spectacularly to about n·log₂n comparisons.

For a handful of 8 numbers the difference between the two methods is negligible. But for a database of a million records the difference means everything: a modern processor settles the merge sort in a fraction of a second (a few tens of millions of operations), whereas selection sort keeps it busy for several minutes, taking hundreds of billions of steps to arrive at exactly the same result.

Complexity

The rate at which the number of operations grows as the volume of input data becomes larger and larger is called computational complexity. In computing we ignore the small details and the secondary constants, keeping only the term that dictates the explosion of effort: we say that selection sort has a complexity of order n² (quadratic growth), while merge sort has a complexity of order n·log n.

Dropping the constants may look like mathematical carelessness, but it is in fact a proof of deep clarity. However much we optimise an algorithm of order n², and however carelessly we program an algorithm of order n·log n, for a large enough volume of data the n·log n algorithm will always outclass the first beyond appeal. Not even buying a supercomputer a thousand times more powerful can save an inefficient algorithm: the brute power of the processor merely postpones a little the moment when the quadratic curve becomes an impassable wall. Complexity is a mathematical trait of the idea itself, not of the physical machine, and that is why it remains true across the centuries, however silicon chips may evolve.

Problems with no good algorithm

So far every task we have analysed had an elegant solution. But computer scientists soon discovered a whole family of problems for which we know exactly what to do, yet for which the computational effort explodes astronomically. Think of a travelling salesman who must visit a hundred cities and is looking for the shortest route. The brute recipe is trivially simple: test every possible route in turn and pick the shortest. The steps can be written in three lines of code. The trouble is that the number of possible routes for a hundred cities far exceeds the number of all the atoms in the observable universe; no computer in the world, however long it ran, could go through that list.

For such complex problems nobody has yet discovered a fast and infallible short cut — and nobody has managed to prove that no such short cut could exist. This dilemma is the most famous open problem in computing and mathematics (known as the “P versus NP” problem). In practice, engineers content themselves with approximate methods that give a reasonably good answer in a short time, with no claim to absolute perfection.

In all these hard cases there is a consolation, though: we know with certainty what the theoretical steps look like, even if they are too many to carry out. But there is a far deeper and more troubling barrier that has nothing to do with the speed of processors. It concerns those everyday tasks that any human being solves without conscious effort in a fraction of a second, but for which nobody in the world can set down a recipe with clear steps: how do we tell a dog from a cat? How do we recognise a friend’s handwriting? How do we catch the irony in a sentence? Here it is not computing power we lack; it is the recipe itself. In the next lesson we shall try to write such a mechanical recipe, only to see exactly where classical logic collapses and why we need an entirely new paradigm: machine learning.