The Mathematics Behind Algorithm Design: What Math You Actually Use

You don’t need advanced math to design useful algorithms, but a small set of ideas shows up again and again: logarithms and growth rates, induction, counting, graphs, probability, and modular arithmetic. Each one answers a practical question. How fast will this run on a million items? Is this loop correct? How many cases are there? Can I trust a random shortcut? This post walks through those ideas with short Python examples, all of which were run.

1. Growth rates and logarithms: how fast will it be?

Big-O notation is a way of comparing how running time grows as input grows. The most useful function to know is the logarithm, because every “halve the problem each step” algorithm (binary search, balanced trees, divide and conquer) has a log in its cost. The base-2 logarithm of n is the number of times you can halve n before reaching 1:

import math
for n in (1_000, 1_000_000, 1_000_000_000):
    print(n, math.ceil(math.log2(n)))
# 1000 10
# 1000000 20
# 1000000000 30

That is why binary search on a billion sorted items needs at most about 30 comparisons, while a linear scan may need a billion. Knowing this table by heart lets you rule out designs quickly: O(n²) on a million items is around a trillion steps, which is too slow; O(n log n) is about twenty million, which is fine.

Recurrences

Recursive algorithms are analyzed by writing their cost as a recurrence. Merge sort splits the input in two, sorts each half, and merges in linear time: T(n) = 2T(n/2) + n. The Master Theorem solves this form and gives O(n log n). You can check the claim by counting directly:

def T(n):
    return 0 if n <= 1 else T(n // 2) + T(n - n // 2) + n

print(T(1024), 1024 * 10)            # 10240 10240
print(T(2**20), 2**20 * 20)          # 20971520 20971520

The count matches n log₂ n exactly for powers of two. If you can write the recurrence for a recursive solution in an interview, you can state its complexity with confidence.

2. Induction and invariants: is it correct?

Mathematical induction proves a statement for all n by proving it for a base case and showing that “true for n” implies “true for n + 1”. That is the same shape as a recursive function: the base case returns directly, and the recursive case assumes the call on the smaller input is correct. If you can argue those two parts, the function is correct.

For loops, the equivalent tool is a loop invariant: a statement that is true before the loop, stays true after every iteration, and implies the answer when the loop ends. Euclid’s algorithm for the greatest common divisor is a clean example. The invariant is that gcd(a, b) never changes, because gcd(a, b) = gcd(b, a mod b):

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print(gcd(1071, 462))   # 21

When a loop is hard to get right (binary search boundaries are the usual one), write the invariant in a comment first, such as “the target, if present, is in a[lo..hi]“. Then check that every branch preserves it.

3. Counting and combinatorics: how many cases are there?

Combinatorics tells you how big a search space is before you try to search it. There are n! orderings of n items and C(n, k) ways to choose k of them. A brute-force solution that tries every permutation is only viable when n! is small:

import math
print(math.factorial(9))     # 362880
print(math.factorial(14))    # 87178291200
print(math.comb(5, 2))       # 10

This is the reason the Traveling Salesman Problem is hard to brute force. With n cities, fixing the starting city leaves (n – 1)! routes to try, and half of those are reverses of the others, so about (n – 1)!/2 distinct tours. For 20 cities that is 60,822,550,204,416,000. Good TSP solvers use dynamic programming (about n²2ⁿ steps), branch and bound, or heuristics instead.

The same arithmetic tells you when to prune a backtracking search, and when a problem asking for “all subsets” (2ⁿ) cannot have a polynomial-time solution that lists them.

4. Graph theory: modeling relationships

A graph is a set of nodes and edges. Once you see a problem as a graph, you can reuse well-understood algorithms: breadth-first search for fewest steps in an unweighted graph, depth-first search for connectivity and cycles, Dijkstra’s algorithm for shortest paths with non-negative weights, topological sort for dependencies. Many interview problems (word ladders, course schedules, islands in a grid) are graph problems that don’t mention graphs.

The math you need is mostly vocabulary and a few facts: a tree is a connected graph with no cycles and n – 1 edges for n nodes; a graph with V nodes and E edges costs O(V + E) to traverse; a dense graph has E close to V², which changes which representation is cheaper. To practice, try BFS Min Distance to Every Vertex and Dijkstra’s Algorithm.

5. Proofs behind greedy and dynamic programming

A greedy algorithm picks the locally best option and never looks back. Whether it is correct is a math question, and the answer is sometimes no. Coin change shows both sides. With coins 1, 3 and 4 and a target of 6, greedy takes 4 + 1 + 1 (three coins), but the best answer is 3 + 3 (two coins). Dynamic programming, which tries every last coin and keeps the best, gets it right:

def greedy(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count

def dp(coins, amount):
    INF = 10**9
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        best[a] = min((best[a - c] + 1 for c in coins if c <= a), default=INF)
    return best[amount]

print(greedy([1, 3, 4], 6), dp([1, 3, 4], 6))   # 3 2

Contrast that with interval scheduling: to fit the most non-overlapping meetings, sort by end time and always take the next meeting that starts after the last one ends. This one is provably optimal, using an exchange argument: any optimal schedule can swap its first meeting for the one that ends earliest without losing anything.

def max_meetings(intervals):
    count, end = 0, float("-inf")
    for s, e in sorted(intervals, key=lambda x: x[1]):
        if s >= end:
            count += 1
            end = e
    return count

iv = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
print(max_meetings(iv))   # 4

A brute-force check over all subsets of these meetings also returns 4. When you’re unsure whether a greedy rule works, look for a small counterexample first, as with coin change, and try an exchange argument if you can’t find one. The Non Overlapping Intervals lesson is a good place to practice this exact pattern.

6. Probability: when randomness helps

Randomized algorithms use random choices to avoid bad cases. Quicksort with a random pivot is the standard example. No fixed input is always slow; the expected number of comparisons is about 2n ln n. A quick simulation on 2,000 distinct values, averaged over 20 runs, gave about 24,500 comparisons, a bit under the 30,400 that 2n ln n predicts because the exact formula subtracts a lower-order term (roughly 2.85n). The growth is what matters: n log n on average regardless of input order.

Two terms to keep straight:

• Las Vegas algorithms always return the correct answer, but their running time is random (randomized quicksort).
• Monte Carlo algorithms run in bounded time but may return an approximate or occasionally wrong answer (estimating a value by sampling, or primality tests such as Miller-Rabin).

Estimating pi by throwing random points at a square is the classic Monte Carlo example. The share of points that land within the unit circle approaches pi/4:

import random
random.seed(0)
N = 1_000_000
inside = sum(1 for _ in range(N)
             if random.random()**2 + random.random()**2 <= 1)
print(4 * inside / N)   # 3.14244

The error shrinks like 1/√N, so each extra digit of accuracy costs a hundred times more samples. That kind of statement, how the error depends on the work, is exactly what the probability behind the algorithm gives you.

Probability also explains hash tables. The birthday paradox says that with 23 people there is already about a 50.7% chance that two share a birthday. Likewise, a hash table with many keys will have collisions long before it is full, so a good design handles collisions rather than hoping to avoid them.

7. Modular arithmetic: keeping numbers small

The remainder operator is everywhere: circular buffers, hashing, checking even or odd, clock problems, and the “answer modulo 10⁹ + 7″ in contest problems. The key rule is that you can reduce at every step, because (a × b) mod m = ((a mod m) × (b mod m)) mod m. Combined with repeated squaring, that gives fast modular exponentiation in O(log e) multiplications:

def mod_pow(b, e, m):
    result, b = 1, b % m
    while e:
        if e & 1:
            result = result * b % m
        b = b * b % m
        e >>= 1
    return result

print(mod_pow(2, 100, 1_000_000_007))   # 976371285
print(pow(2, 100, 1_000_000_007))       # 976371285 (built-in)

The same squaring idea computes ordinary powers and matrix powers (such as Fibonacci in O(log n)). Public-key cryptography is built on this arithmetic.

How much math should you study?

For coding interviews, the first four sections cover most of what you need: growth rates, recurrences, induction-style reasoning, counting, and basic graph facts. Probability and number theory show up less often but are common in competitive programming, data engineering, security and machine learning. A reasonable order is:

1. Logarithms, powers and summations, enough to compute and compare Big-O.
2. Counting: permutations, combinations, 2ⁿ subsets.
3. Induction and invariants, by writing a one-line justification for each loop you write.
4. Graph basics, then probability and modular arithmetic as the problems demand.

Our posts on essential math skills for programming and applying mathematical induction in algorithm design go further into the first and third items.