How Fast Can an Algorithm Go?

Alan Turing's 1936 model defines computation itself, an infinite tape and a finite rule table, powerful enough to describe anything a general purpose computer can do. Every algorithm on this trail is, in the end, something a Turing machine could carry out.

A procedure that solves a problem by calling itself on a smaller version of the same problem, until a base case stops it. The mathematics behind it goes back to Alonzo Church and Kurt Godel in the 1930s, and John McCarthy brought it into practical programming with Lisp around 1958 to 1960.

Pick a pivot, split everything else into smaller and larger, and sort each side the same way. Quicksort is recursion put to work on one of computing's most common tasks, sorting a list.

Hoare invented quicksort and later wrote An Axiomatic Basis for Computer Programming in 1969, a founding paper for reasoning formally about whether a program is correct.

Conceived in 1956 and published in 1959, Dijkstra's algorithm grows the set of nodes whose shortest distance is settled, always extending it through the nearest unsettled node until it reaches the destination. It is the standard answer to finding the shortest path through a network.

Dijkstra invented the shortest path algorithm that carries his name and later led the structured programming movement, arguing against unrestricted goto statements in his 1968 letter Go To Statement Considered Harmful.

Big O notation expresses that a function's growth is bounded above by another, simpler function, letting algorithms like quicksort and Dijkstra's algorithm be compared by growth rate rather than by counting exact operations.

An NP complete problem is one where, if any single one of them could be solved in polynomial time, every problem in NP could be solved that fast too. That tight link, established in 1971, is why NP completeness sits right next to the open question of P versus NP.

Whether every problem whose solution can be checked quickly can also be solved quickly is one of the seven Millennium Prize Problems, unresolved since Stephen Cook posed it precisely in 1971. Most computer scientists suspect the answer is no, but nobody has proved it either way.