Recognizing O(N!) Factorial Time Complexity
Explore Factorial Time complexity, the absolute worst mathematically possible scaling factor, found in permutations and naive brute-force solvers.
The Absolute Worst Case
If O(N^2) is bad, and O(2^N) is terrible, O(N!) Factorial Time is apocalyptic. It is the steepest, most catastrophic time complexity in computer science.
What is Factorial Math?
A factorial (denoted by !) is the product of all positive integers less than or equal to N.
- 3! = 3 * 2 * 1 = 6
- 5! = 5 * 4 * 3 * 2 * 1 = 120
- 10! = 3,628,800
- 15! = 1.3 Trillion
If an algorithm is O(N!), adding just one or two elements to the dataset forces the operations into the trillions.
Where Does O(N!) Occur?
Factorial time almost exclusively occurs when you are generating Permutations finding every possible arrangement of a set of items.
- The Traveling Salesperson Problem (Brute Force): Finding the shortest route to visit N cities by calculating every single possible order of visits.
- Generating Anagrams: Finding every possible word arrangement from a set of letters.
The Algorithm Structure
O(N!) usually appears in recursive backtracking algorithms. The code typically involves a loop that iterates N times. Inside that loop, it recursively calls itself N-1 times, which loops and calls itself N-2 times, and so on.
The Takeaway
If your algorithm's time complexity is O(N!), it is practically unusable for any input size larger than 12. In technical interviews, if you must generate permutations, O(N!) is mathematically unavoidable, but you are expected to use Backtracking to abandon invalid permutations as early as possible.
It is an extreme time complexity where the operations multiply factorially (N * N-1 * N-2...), representing the absolute worst algorithmic scaling possible.
Problems that require generating all possible permutations (orderings) of a dataset, such as solving the brute-force Traveling Salesperson problem.
Yes, drastically worse. 20^2 is 400. 2^20 is 1 Million. 20! is 2.4 Quintillion.
You cannot change the math of permutations, but you can use Dynamic Programming or Branch and Bound techniques to skip evaluating branches that are guaranteed to be invalid.
Only if the problem explicitly asks for all permutations or combinations. If they ask for a shortest path or optimal solution, an O(N!) brute force is just a starting point.