What is an algorithm? Step-by-step instructions, explained

An algorithm is a finite list of exact, step-by-step instructions that solves a problem or completes a task: given an input, it always reaches an answer in a limited number of steps, with no guessing about what to do next. A recipe is a loose everyday example. Computers run on algorithms, and the same problem can often be solved by algorithms that differ in speed by a factor of thousands.

In short

• An algorithm must be exact (every step clear), finite (it stops) and effective (each step can actually be carried out), turning inputs into an output.
• Different algorithms for the same job can differ enormously: finding a name in a 1,000-page phone book takes up to 1,000 looks one way and at most 10 another.
• "The algorithm" on social media means the ranking system that picks what each person sees, usually a model learned from data.

What makes something an algorithm?

Computer scientists hold an algorithm to a stricter standard than a recipe. The usual list, from the computer scientist Donald Knuth's textbook The Art of Computer Programming, has five properties (Wikipedia):

1. Finiteness: it always stops after a finite number of steps.
2. Definiteness: every step is precisely defined, with no room for interpretation.
3. Input: it takes zero or more values to work on.
4. Output: it produces at least one result that relates to the input.
5. Effectiveness: every step is basic enough to be done exactly, in principle even with pencil and paper.

A recipe that says "season to taste" fails definiteness. Instructions that say "keep stirring until it looks right" may never stop. The NIST Dictionary of Algorithms and Data Structures puts it in one line: "a computable set of steps to achieve a desired result." An algorithm is an idea, not code: the same algorithm can be written in any programming language, or carried out by a person.

The word comes from the name of al-Khwarizmi, a Persian scholar in Baghdad whose book on calculating with Indian numerals, written around 825, was translated into Latin in the 12th century as Algoritmi de numero Indorum. The idea is far older. One of the oldest algorithms still in use is Euclid's, from his Elements of about 300 BC, for finding the largest whole number that divides two others. For 1,071 and 462: divide 1,071 by 462, which goes 2 times with 147 left over; divide 462 by 147, 3 times with 21 left over; divide 147 by 21, 7 times with nothing left over. The last divisor, 21, is the answer (Wikipedia). Here it takes three divisions; for any two whole numbers, the remainders keep shrinking, so it is guaranteed to stop.

How do two algorithms for the same job compare? The phone book

Suppose you need to find "Martinez" in a printed phone book of 1,000 pages, with the names in alphabetical order.

Algorithm 1: page by page. Start at page 1. If the name isn't there, turn to the next page. Repeat. In the worst case, the name is on the last page and you look at all 1,000. On average, over many searches, you look at about 500.

Algorithm 2: halving. Open the book in the middle, at page 500. If "Martinez" comes before the names there alphabetically, you can tear away the back half, because the name can't be in it; otherwise tear away the front half. Open what's left in its middle and repeat. Each look halves the pages that remain:

Look	Pages left to search
Start	1,000
1	500
2	250
3	125
4	63
5	32
6	16
7	8
8	4
9	2
10	1

After at most 10 looks, one page is left. The reason is that 2 multiplied by itself 10 times is 1,024, more than 1,000. This algorithm is called binary search, and the computing pioneer John Mauchly described it in 1946 (Wikipedia). The gap widens with size. For a book of a million pages, page by page takes up to a million looks; halving takes at most 20, because 2 to the 20th power is just over a million. For a billion, 30.

The halving algorithm comes with a condition: the names must be in order. On a shuffled list, it fails, and page by page is the only safe choice. Algorithms rarely work alone; they depend on how the data are arranged, which is why computer scientists study them alongside data structures.

How does a computer sort a list?

Sorting, putting items in order, is one of the most studied problems in computing, partly because so much else, like binary search, needs sorted data first. Two ways to sort 1,000 numbers:

Selection sort. Scan the whole list for the smallest number and move it to the front. Scan the remaining 999 for the next smallest, then the remaining 998, and so on. The number of comparisons is 999 + 998 + … + 1 = 499,500.

Merge sort. Split the list in half, sort each half, then merge the two sorted halves by repeatedly taking the smaller of the two front items. Each half is sorted the same way, split again and again until the pieces have one item, which is already sorted. Merging two sorted lists of total length n takes at most n − 1 comparisons, and the list can be halved only about 10 times, so the whole sort takes fewer than 10,000 comparisons: at most 8,977 for 1,000 numbers.

That is about 56 times fewer comparisons than selection sort, and the ratio grows as lists get longer: for a million items it is tens of thousands of times. Merge sort calls itself on smaller pieces, an approach called recursion. The way a method's step count grows with the size of its input is what Big O notation describes: page by page and selection sort grow in proportion to n and to n² respectively, binary search to log n, and merge sort to n log n.

What is "the algorithm" on social media?

When people say "the algorithm" decides what they see, they mean a platform's ranking system: the software that chooses, from the thousands of posts and videos that could be shown, which few appear at the top of a feed and in what order. It is less one algorithm than a pipeline of them. Typically, one stage gathers candidate posts, a model scores each by how likely this person is to watch, like, share or reply, and a final stage orders them, often with rules mixed in, such as limits on repeated content.

Two features set these systems apart from the phone book. First, the scoring model is usually learned from data rather than written by hand, so no engineer specifies which videos you'll see; the system adjusts its predictions from what millions of people do, which is how machine learning works. Second, the platform chooses what to optimize, such as time watched or interactions, and the ranking pursues that goal, which can differ from what a user would pick on reflection. Search engines rank too, by relevance to the words typed rather than by predicted engagement, a process the note on search engines takes apart.

What do people get wrong about algorithms?

The commonest mistake is to think of an algorithm as something only computers have, or as something mysterious. Long division, the steps for tying a knot and the rules for a fire drill are algorithms if they are exact and finite. Computers make algorithms matter more because they execute billions of steps a second, as the note on how computers work explains, so the choice between a 10-step and a 1,000-step method is multiplied across every search, sort and request.

A second mistake is to equate a faster computer with a faster answer. Hardware a thousand times faster cuts every running time by a thousand. A better algorithm can cut the work from a million steps to 20, and the advantage keeps growing with the size of the problem. Some problems seem to have no fast algorithm at all; whether they truly don't is the open question of P vs NP.

Check yourself

• Without looking back, explain why halving finds a page in a 1,000-page book in at most 10 looks.
• Which of Knuth's five properties does "cook until done" break, and why?
• Why can a better algorithm beat a faster computer?

Sources

• Algorithm — NIST Dictionary of Algorithms and Data Structures
• Algorithm — Wikipedia
• Binary search — Wikipedia
• Euclidean algorithm — Wikipedia
• Merge sort — Wikipedia