# O(n!) - Factorial Time

> The worst standard complexity. n=20 means 2.4 quintillion operations. Brute-force only.

- **Category**: Big O
- **Subcategory**: complexity
- **Canonical URL**: https://designpattern.fyi/big_o/factorial-time/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
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.



## Implementation Example

```javascript
// 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

```



## Trade-offs


### 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




### Considerations & Drawbacks

- 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







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)