Computational Complexity Explorer

Growth Rate

Problem size n 10

Travelling Salesman

Number of cities 6

Routes examined

Total routes — O(n!)

–

Best length so far

–

Verify a route — O(n)

instant

How it works

The top chart plots the operation count of six classic complexity classes across problem size n on a logarithmic y-axis, so O(1) and O(2ⁿ) can share one picture. At 1 billion operations per second, the same n produces wildly different wall-clock times — the panel converts each curve's operation count at the current n into a real duration.

The bottom panel is the Travelling Salesman Problem: find the shortest closed tour visiting every city once. Checking whether a given tour's total length is under some bound K takes O(n) time — just sum the edges. Finding the optimal tour by brute force means trying every permutation of the other n−1 cities: (n−1)! routes, fixing the start city to avoid counting rotations. That is the everyday shape of P vs NP: verification is cheap, exhaustive search is not.

time(n) = operations(n) / 1e9 s
O(2^n):  30  -> ~1.07s     40 -> ~18.3 min
O(n!):    8! =  40320 routes (fixed start: 7! = 5040)
         15! ≈ 1.3e12 routes — brute force stops being an option

Problem size n — moves the cursor along all six growth curves at once and recomputes real times for each.
Number of cities — sets how many stops the salesman must visit; each extra city multiplies the search space by roughly n.
Solve via brute force — steps through permutations in lexicographic order, drawing the current candidate route and keeping the shortest tour found; the counter shows how fast the space is exhausted.

Real-world relevance: routing, chip layout, protein folding and scheduling are all NP-hard in the same way TSP is — practical solvers use heuristics (nearest-neighbour, simulated annealing, branch-and-bound) rather than brute force once n grows past a couple dozen.

Growth rate comparison (log scale)

Travelling Salesman — brute force search

Computational Complexity Explorer