STUDY GUIDE · ABOUT 12 MIN READ

Algorithms

An algorithm is a precise recipe for solving a problem. A good one can turn a hundred steps into seven. Pick a secret number and watch binary search find it by halving the range each time.

BINARY SEARCH · 1 TO 100
1100
Range 1-100. First guess: the middle.
Never more than 7 guesses for 100 numbers.

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
CORE CONCEPT

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.

62941017385
Ten unsorted numbers. Press play or step forward.
0comparisons
0swaps
Bubble sortRepeatedly compare neighbours and swap them if they're out of order. Big numbers 'bubble' to the end.O(n²): simple but slow
comparingin final placewaiting
BIG O NOTATION

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.

O(1)array lookup1 ns
O(log n)binary search6 ns
O(n)linear search86 ns
O(n log n)merge sort553 ns
O(n²)bubble sort7.4 µs
O(2ⁿ)brute-force subsets10^9 years
Bars use a logarithmic scale; otherwise all but the last would be invisible. Times assume exactly n, n², etc. steps at 10⁹ steps per second.
DESIGN PARADIGMS

Five strategies behind most algorithms

STRATEGYTHE IDEAYOU MEET IT IN
Divide and conquerSplit the problem into halves, solve each, combine the answers.Merge sort, binary search, fast multiplication
GreedyTake the best-looking option at each step and never look back. Fast, but not always optimal.Making change with coins, Dijkstra's shortest paths
Dynamic programmingBreak a problem into overlapping sub-problems and remember each answer so it's computed once.Spell-check edit distance, route planning, DNA alignment
Graph searchExplore connections systematically, breadth-first or depth-first.Maps, social networks, solving mazes and puzzles
Brute forceTry every possibility. Guaranteed to work, often far too slow.Cracking short passwords, small puzzles, testing other algorithms

Older than computers

Algorithms were being written on clay and papyrus two thousand years before anyone built a machine to run them.

c. 1600 BCBabylonian tabletsStep-by-step procedures for division and square roots, pressed into clay.
c. 300 BCEuclid's algorithmFinds the greatest common divisor of two numbers. Still used in cryptography today.
c. 820Al-KhwārizmīHis books on Hindu-Arabic arithmetic gave us the word 'algorithm'.
1959QuicksortTony Hoare's sorting method, still among the fastest in practice.
1977RSARivest, Shamir and Adleman's public-key encryption made secure online payments possible.
1998PageRankLarry Page and Sergey Brin ranked web pages by the links pointing to them.

Further reading

Introduction to Algorithms· Cormen, Leiserson, Rivest & Stein1990
The Art of Computer Programming· Donald Knuth1968-
Grokking Algorithms· Aditya Bhargava2016
Algorithms to Live By· Brian Christian & Tom Griffiths2016

Algorithmic thinking is logical thinking. Measure yours.

Our full IQ test covers logical, numerical, verbal and spatial reasoning: 60 questions, about 30 minutes.

Take the full IQ test