The Mathematics of Algorithms

The word "algorithm" comes from the name of a mathematician. Muhammad ibn Musa al-Khwarizmi worked in Baghdad around 820 AD, and his book on Hindu-Arabic numerals was translated into Latin as Algoritmi de numero Indorum. "Algoritmi" was his name, and it became the word for a step-by-step procedure.

That origin is fitting. An algorithm is a piece of mathematics. Proving it works, measuring how fast it runs and knowing its limits all require mathematical reasoning. And one of the most important open questions about algorithms comes with a $1 million prize.

Testing Can't Prove an Algorithm Correct

You can run an algorithm on a million test cases and never see a bug, yet it can still be wrong for the million-and-first. Tests show the presence of bugs, never their absence, a point the computer scientist Edsger Dijkstra famously made.

The only way to be certain is proof. That's why the theory of algorithms rests on mathematical tools: invariants, induction and recurrences.

One of the Oldest Algorithms: Euclid's

Around 300 BC, Euclid described how to find the greatest common divisor of two numbers:

gcd(a, b) = gcd(b, a mod b),   and gcd(a, 0) = a

For gcd(1071, 462):

1071 mod 462 = 147
 462 mod 147 = 21
 147 mod 21  = 0   → gcd = 21

Three steps. Try it with the GCF calculator.

Proving Correctness: Invariants

A loop invariant is a statement that's true before and after every iteration. If it's true at the start, stays true each step, and implies the right answer when the loop ends, the algorithm is correct.

For Euclid's algorithm, the invariant is:

The gcd of the current pair equals the gcd of the original pair.

It holds because any number dividing both a and b also divides a mod b = a − qb, and vice versa. When b reaches 0, gcd(a, 0) = a, so the answer is correct.

You also need termination: each step strictly decreases b, and a non-negative integer can't decrease forever. This style of reasoning is closely related to mathematical induction.

An Insider Reference: Lamé's 1844 Analysis

How many steps can Euclid's algorithm take? In 1844, French mathematician Gabriel Lamé proved that the number of steps is at most five times the number of decimal digits of the smaller number.

The worst case happens with consecutive Fibonacci numbers, where each remainder is as large as possible. Lamé's result is often cited as one of the first rigorous analyses of an algorithm's running time, well over a century before computer science existed as a field. See the connection in Fibonacci Numbers: The Sequence That Keeps Appearing Everywhere.

Measuring Speed: Recurrence Relations

Divide-and-conquer algorithms split a problem into smaller copies of itself. Their running time is naturally a recurrence.

Merge sort splits a list in half, sorts both halves, and merges them in linear time:

T(n) = 2T(n/2) + n

Unroll it: at each level of splitting, the total merging work is n, and there are log₂ n levels. So:

T(n) = n log₂ n

The master theorem solves recurrences of the form T(n) = aT(n/b) + f(n) in general. For binary search, T(n) = T(n/2) + 1 gives log₂ n. Explore logs with the base-2 logarithm table.

Lower Bounds: How Fast Can Anything Be?

Mathematics can prove that no algorithm does better than some limit.

A comparison-based sort must distinguish between all n! possible orderings of n items. Each comparison has two outcomes, so k comparisons can distinguish at most 2ᵏ orderings. We need:

2ᵏ ≥ n!   →   k ≥ log₂(n!) ≈ n log₂ n

So merge sort's n log n isn't just good. For comparison sorting, it's optimal.

Dynamic Programming

Computing Fibonacci numbers directly from F(n) = F(n−1) + F(n−2) recomputes the same values again and again, taking exponential time. Storing each result once reduces it to linear time.

This technique, dynamic programming, was developed by mathematician Richard Bellman in the 1950s. He later wrote that he chose the name partly because it sounded impressive and hid the mathematical nature of his research from officials who disliked the word "research."

The Limits: P vs. NP

Some problems seem to have no fast solution. The traveling salesman problem asks for the shortest route visiting every city once. Checking a proposed route is easy, but finding the best one appears to require exploring an exponential number of possibilities.

In 1971, Stephen Cook formalized the question: are problems whose solutions can be checked quickly (the class NP) always problems that can be solved quickly (the class P)?

Nobody knows. In 2000, the Clay Mathematics Institute named P vs NP one of its seven Millennium Prize Problems, with a $1,000,000 reward. Most researchers believe P ≠ NP. If that's wrong, much of modern cryptography would collapse.

Two Concepts Worth Knowing

Loop Invariant

A loop invariant is a condition that holds at the start of every loop iteration. It's the main tool for proving iterative algorithms correct.

Recurrence Relation

A recurrence relation defines a quantity in terms of smaller instances of itself. It's the natural way to describe the running time of recursive algorithms. See the algebra formulas for related series.

Quick Answer: How Is Math Used in Algorithms?

Mathematics proves algorithms correct using invariants and induction, measures their efficiency with Big-O notation and recurrence relations, establishes lower bounds on what any algorithm can achieve, and classifies problems by difficulty, as in the open P vs NP question.

Try Them Yourself

• GCF Calculator: run Euclid's algorithm
• LCM Calculator: built directly from the GCD
• Base-2 Logarithm Table: how divide-and-conquer scales
• Number Theory Formulas: the math behind Euclid
• Why Every Programmer Should Understand Big-O Notation: growth rates in practice
• Alan Turing and the Turing Machine: what can be computed at all

Run Euclid's algorithm on two consecutive Fibonacci numbers, like 89 and 55. Count the steps, then check Lamé's bound. You've just found the algorithm's worst case.