Factorial Time O(n!) — The Most Intractable Complexity

What Is O(n!) Factorial Time?

O(n!) is the complexity class where the number of operations equals the factorial of the input size. n! = n × (n-1) × (n-2) × ... × 1.

Growth Rate

n	n!
5	120
10	3,628,800
12	479,001,600
15	1,307,674,368,000
20	2,432,902,008,176,640,000

At n = 20, the number of operations exceeds 2.4 quintillion — far beyond what any computer can handle in a reasonable time.

Why Factorial Grows So Fast

Factorial grows faster than exponential. For any base b, eventually n! > bⁿ. At n = 13, n! already exceeds 2¹³ and 3¹³.

Classic O(n!) Algorithms

Traveling Salesman Problem (Brute Force)

To find the shortest route visiting n cities exactly once, the brute-force approach tries all (n-1)!/2 possible routes. For 15 cities, that’s over 43 billion routes.

Generating All Permutations

Listing every possible ordering of n items produces exactly n! permutations. Heap’s algorithm does this in O(n!) time, which is optimal since the output itself has n! elements.

Bogosort

The joke sorting algorithm that randomly shuffles the array and checks if it’s sorted. Expected time: O(n × n!).

Practical Solutions

For problems with factorial complexity:

• Dynamic Programming + Bitmask: TSP can be solved in O(n² × 2ⁿ) using Held-Karp, which is exponential but vastly faster than factorial.
• Branch and bound with good heuristics.
• Approximation algorithms: Christofides’ algorithm gives a 1.5-factor approximation for metric TSP in polynomial time.
• Genetic algorithms and other metaheuristics for large instances.