Primer: algorithms and complexity

Read first

• Nothing. If you can read a short Python function, you have everything this primer needs.

The question this primer answers: how do you measure the work an algorithm does, and why does that measurement decide which routing methods can run on real instances?

Intuition

Every post in this series runs on the same eight stops. Coordinates are in kilometres; distances are rounded to units of 100 m. The best tour, A-B-C-D-H-E-F-G-A, costs 315.

Counting steps

To compare algorithms we count their basic steps instead of timing them. Timing depends on the machine and the language; the count depends only on the algorithm and the size of the input, usually n, the number of stops.

The simplest step is pricing one tour. Each leg is one lookup and one addition, so a tour of n stops costs n additions. The heatmap prices the best tour; the strip underneath is the eight additions.

Double the stops and pricing takes twice as many additions. That is linear growth.

Recursion: trying every tour

To find the best tour by brute force, as in Post 2, we have to try every order of the stops. The cleanest way to write that is recursion: a function that solves a problem by calling itself on a smaller version of it.

Start a path at A. If no stops are left, the path is a complete tour: price it. Otherwise, for each stop that is left, add it to the path and solve the smaller problem of finishing that path. The first case is the base case, which stops the recursion; the second is the recursive case, which shrinks the problem by one stop every time.

Each call branches into one call per remaining stop. The diagram shows the top of the tree of calls.

flowchart TD
  R["A (7 stops left)"] --> AB["A-B (6 left)"]
  R --> AC["A-C (6 left)"]
  R --> AX["A-D … A-H: 5 more"]
  AB --> ABC["A-B-C (5 left)"]
  AB --> ABD["A-B-D (5 left)"]
  AB --> ABX["A-B-E … A-B-H: 4 more"]
  ABC --> L["… down to 0 left: price the tour"]

The search goes depth first: it follows one branch all the way down to a complete tour before backing up to try the next choice. Step through the first branch it takes, and the branch that wins.

The number of calls at each depth is the product of the choices made so far:

The 5,040 calls at the bottom are complete tours, each priced with 8 additions. Every tour appears twice, once in each direction, which is why Post 2 counts 5,040 / 2 = 2,520 distinct tours.

Arrays, linked lists and heaps

How you store a tour changes what each step costs. Take the nearest-neighbour tour from Post 9, A-G-E-D-H-C-B-F.

• An array (a Python list) keeps the stops in numbered slots, 0 to 7. Slot 5 holds C, and you can read it in one step, wherever it is.
• A linked list keeps, for each stop, a pointer to the next one: A → G, G → E, E → D, and so on. To reach the sixth stop you start at A and follow five pointers.

Neither wins every row. Post 13 shows why routing codes usually store the tour as an array plus a position table, and what more elaborate structures buy.

A heap answers a different question: which item is smallest? Nearest-neighbour search, Dijkstra’s shortest paths and Prim’s minimum spanning tree all repeatedly ask for “the closest one not yet used”. A heap keeps items in a tree in which every parent is no larger than its children, so the smallest is always at the top. Adding an item or removing the smallest takes about log₂ n steps, because each only travels one path between the top and the bottom of the tree. Put in the distances from A in any order, and they come out sorted:

J. W. J. Williams introduced the heap in 1964, as the data structure behind his sorting algorithm, heapsort.

The formal idea

Big-O. Let f(n) be the number of steps an algorithm takes on an input of size n, and g(n) a simple function such as n² or 2ⁿ. We write

f(n) = O(g(n))   if there are constants c > 0 and n₀ such that
                 f(n) ≤ c · g(n) for every n ≥ n₀

In words: beyond some size, f grows no faster than g, up to a constant factor. The constant c absorbs the machine’s speed; n₀ means small inputs don’t count. Pricing a tour takes n additions, so it is O(n). Nearest neighbour checks up to n stops at each of n steps, so it is O(n²).

Big-O is an upper bound. Knuth (1976) proposed definitions for two companions that are now standard: f(n) = Ω(g(n)) means f grows at least as fast as g, and f(n) = Θ(g(n)) means both, so g is the exact growth rate up to constants. The O symbol itself is older: it comes from number theory, from Bachmann’s 1894 book, and was popularised by Landau in 1909.

Growth rates. The table compares the functions that appear in this series. log₂ n is the number of times you can halve n before reaching 1.

An algorithm is polynomial if its step count is O(nᵏ) for some fixed k: n, n log n, n² and n³ all qualify. It is exponential if the count grows like cⁿ for some c > 1, or faster: 2ⁿ and n! both qualify, and n! eventually outgrows cⁿ for every c. At n = 8 the two families are close; 2⁸ is smaller than 8³. By n = 52, the size of berlin52, they are in different worlds.

The decisive difference shows when you buy a faster computer. Suppose one hour of computing at 10⁹ steps per second, then a machine 1,000 times faster:

For polynomial algorithms, faster hardware multiplies the size you can handle. For exponential ones, it adds a few stops. Garey and Johnson (1979) made this point with a similar table in the first chapter of their book on NP-completeness, and it is why Post 2’s question, whether the TSP has a polynomial algorithm at all, matters so much.

The algorithms in this series. Most of them land in one of these classes:

Common misconceptions

“An O(n) algorithm is always faster than an O(n²) one.” Only for large enough n. Big-O hides the constant c, so an O(n²) method with a tiny constant can win on small inputs. The definition only promises what happens beyond n₀.

“Exponential only matters for huge instances.” berlin52 is small: 52 cities. Yet 2⁵² is about 4.5 × 10¹⁵ and 52! about 8.1 × 10⁶⁷. Exponential growth is a problem from a few dozen stops on, which is why most of this series is about methods that avoid it.

“Recursion is slow, so avoid it.” Recursion is a way of writing an algorithm, not a speed. The 13,700 calls above are slow because brute force tries every order, and a loop that tried every order would be just as slow. Held-Karp (Post 4) is the same recursion with its answers stored and reused, and that changes O(n!) into O(n² · 2ⁿ).

“Linked lists are faster for routing because inserting is O(1).” Inserting is, but finding where to insert, or which stop is in position k, is not. And reversing a stretch of a tour, the core of 2-opt, flips every pointer in it. Post 13 works through the trade-offs.

Try it in Python

The script finds the best tour of the eight stops with the recursion above and counts its calls. It then checks the tour-count formula (n − 1)!/2 by brute-force counting for 4 to 10 stops, and shows a heap returning the stops nearest to A first. It uses only the standard library.

import heapq
import math
from itertools import permutations

stops = {"A": (2, 2), "B": (6, 1), "C": (9, 3), "D": (8, 7),
         "E": (5, 9), "F": (1, 8), "G": (4, 5), "H": (10, 9)}
d = {a: {b: round(10 * math.dist(stops[a], stops[b])) for b in stops} for a in stops}

def cost(tour):  # n additions: one per leg, including the leg back to the start
    return sum(d[tour[i]][tour[(i + 1) % len(tour)]] for i in range(len(tour)))

def best_tour(path, left):
    """Cheapest way to extend path through every stop in left. Returns (cost, tour, calls)."""
    if not left:  # base case: a complete tour
        return cost(path), path, 1
    best_cost, best, calls = math.inf, None, 1
    for stop in sorted(left):  # recursive case: try each stop next
        c, tour, k = best_tour(path + [stop], left - {stop})
        calls += k
        if c < best_cost:
            best_cost, best = c, tour
    return best_cost, best, calls

c, tour, calls = best_tour(["A"], set(stops) - {"A"})
print(f"optimum {c}: {'-'.join(tour)}-A, after {calls} calls")

# 1. Counting tours: brute force against the formula (n - 1)!/2
for n in range(4, 11):
    counted = sum(1 for p in permutations(range(1, n)) if p[0] < p[-1])  # drop mirror images
    print(f"n = {n:>2}: counted {counted:>7}, formula {math.factorial(n - 1) // 2:>7}")

# 2. A heap hands back the smallest item first, whatever order items went in
heap = []
for stop in "BCDEFGH":
    heapq.heappush(heap, (d["A"][stop], stop))  # O(log n) per push
print("nearest to A first:", [heapq.heappop(heap) for _ in range(len(heap))])  # O(log n) per pop

The first line of output is optimum 315: A-B-C-D-H-E-F-G-A, after 13700 calls, matching the depth table. The tour counts:

The heap returns the stops in the order of the heap table above. The counts match the formula exactly, and each extra stop multiplies the count by a bigger factor: factorial growth, which no fixed power of n keeps up with.

Exercise

Add a ninth stop to the eight. How many calls would best_tour make, and how many complete tours would it price? Then compare: how many additions does it spend pricing tours, against how many calls it makes in total?

Hint: the depth table multiplies by the number of stops still left at each level. With eight stops after A, the first multiplier is 8.

Where to go next

• Post 2: Why is the TSP hard? runs brute force for real and explains P vs NP and NP-hardness.
• Post 4: Dynamic programming: Held-Karp turns the recursion above into O(n² · 2ⁿ) by remembering answers.
• Post 13: Making local search fast puts arrays, linked lists and position tables to work on 2-opt.
• Primer C: linear and integer programming is the next primer, for the exact methods of Parts 2 and 3.

References

• Bachmann, P. (1894). Die analytische Zahlentheorie (Zahlentheorie, Part 2). Teubner, Leipzig.
• Landau, E. (1909). Handbuch der Lehre von der Verteilung der Primzahlen. 2 vols. Teubner, Leipzig.
• Williams, J. W. J. (1964). “Algorithm 232: Heapsort.” Communications of the ACM 7(6): 347–348.
• Knuth, D. E. (1976). “Big Omicron and Big Omega and Big Theta.” SIGACT News 8(2): 18–24.
• Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed. Addison-Wesley.
• Garey, M. R., and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2022). Introduction to Algorithms, 4th ed. MIT Press.
• Python Software Foundation. “heapq — Heap queue algorithm.” Python 3 documentation.

See the whole series · ← All writing