What an algorithm is, in short
An algorithm is a finite, unambiguous sequence of steps that turns an input into an output, such as a list into a sorted list or two places into the shortest route between them. Studying algorithms means designing these steps and measuring how their cost grows as the input gets bigger.
The word comes from al-Khwārizmī, a 9th-century Persian mathematician in Baghdad whose name, Latinised as Algoritmi, came to mean calculating with Hindu-Arabic numerals.
- Must be
- Finite, precise, effective, with clear input and output
- Measured by
- Time and memory as input grows (Big O)
- Oldest known
- Euclid's GCD method, c. 300 BC
- Not the same as
- A program, which is one implementation of it
Same list, three ways to sort it
Sorting is the classic algorithm problem. Pick a method and play it. Watch the counters: different strategies do very different amounts of work on the same ten numbers.
Why growth matters more than speed
Big O describes how the number of steps grows with input size n. Slide n up and see how long each kind of algorithm would take on a computer doing a billion steps per second.
Five strategies behind most algorithms
Older than computers
Algorithms were being written on clay and papyrus two thousand years before anyone built a machine to run them.