Back to Catalog
Big O
Danger Zone
O(n!) - Factorial Time
The worst standard complexity. n=20 means 2.4 quintillion operations. Brute-force only.
Intent & Description
Real-world Use Case
Brute-force TSP (Travelling Salesman): find the shortest route visiting 20 cities ā 20! = 2.4 quintillion routes to check. Held-Karp DP reduces this to O(nĀ² 2āæ) = about 400M operations for n=20. Still slow, but actually computable.
Source
š TL;DR
O(n!) = the nuclear option. n=15 takes minutes, n=20 takes geological time. Never acceptable in production for n > 10. Use DP, heuristics, or approximation algorithms instead.
Advantages
- Guaranteed to find the optimal solution (if you can wait for it)
- Simple to implement ā just generate all permutations
- Valid for very small n (sorting 5 items by trying all orders, seating 6 guests)
- Useful in competitive programming for brute-force verification of smarter algorithms
Disadvantages
- Completely infeasible for n > 12-15 in any practical context
- n=20 would take longer than the life of the universe on modern hardware
- Almost all O(n!) problems have known polynomial-time approximation algorithms
- If your production code has O(n!) complexity, it is a critical bug regardless of current n
Implementation Example
// O(n!) ā Generate all permutations (only feasible for n ā¤ ~10)
function permutations(arr) {
if (arr.length <= 1) return [arr];
const result = [];
for (let i = 0; i < arr.length; i++) {
const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
for (const perm of permutations(rest)) { // Recursive ā n! total calls
result.push([arr[i], ...perm]);
}
}
return result;
}
// n=10: 3,628,800 permutations ā manageable
// n=15: 1,307,674,368,000 ā will take minutes
// n=20: 2,432,902,008,176,640,000 ā will never finish
// O(n!) ā Brute-force TSP (never use in production for n > 10)
function tspBruteForce(distances) {
const n = distances.length;
const cities = Array.from({ length: n - 1 }, (_, i) => i + 1);
let minDist = Infinity, bestRoute = null;
for (const perm of permutations(cities)) {
const route = [0, ...perm, 0];
const dist = route.reduce((acc, c, i) =>
i === 0 ? 0 : acc + distances[route[i-1]][c], 0);
if (dist < minDist) { minDist = dist; bestRoute = route; }
}
return { minDist, bestRoute };
}
// ā
For real TSP ā use nearest-neighbor heuristic (O(nĀ²), ~25% above optimal)
// or Held-Karp DP (O(nĀ² 2^n)) for exact but feasible solutions up to nā20