Introduction

When people ask for an example of O(n!), they are usually asking about algorithms that enumerate every possible ordering of n items. Factorial growth is one of the fastest common complexity classes, which is why it becomes impractical at surprisingly small input sizes.

Why O(n!) Grows So Quickly

n! means multiplying every integer from 1 through n. That gives explosive growth:

• '5! = 120'
• '8! = 40320'
• '10! = 3628800'

This is why factorial-time algorithms are only usable for small values of n or when an exact exhaustive search is unavoidable. Even if each step is cheap, the number of possibilities dominates the running time.

A classic source of O(n!) is permutation generation. If you have n distinct elements, there are exactly n! different orderings. Any algorithm that must examine all of them has at least factorial growth.

A Concrete Permutation Example

The Python function below prints every permutation of a list by using backtracking. It is a real example of factorial work because it must visit every possible ordering.

1def permute(items, start=0):
2    if start == len(items):
3        print(items)
4        return
5
6    for i in range(start, len(items)):
7        items[start], items[i] = items[i], items[start]
8        permute(items, start + 1)
9        items[start], items[i] = items[i], items[start]
10
11numbers = [1, 2, 3]
12permute(numbers)

For 3 elements, the function prints 6 permutations. For 4, it prints 24. For 10, it would need to produce 3628800 orderings. The recursive overhead is not the real problem; the number of valid outcomes is.

This is the reason the complexity is written as O(n!) rather than O(n), O(n^2), or even O(2^n). Every extra element multiplies the total work by a larger factor than the previous step.

Where Factorial Time Appears in Real Problems

The most common real-world appearance is brute-force search over permutations. The traveling salesperson problem is the standard teaching example. If you try every possible city order and compute the tour cost, you end up with factorially many candidate routes.

1from itertools import permutations
2
3def brute_force_tsp(dist):
4    cities = range(1, len(dist))
5    best_cost = float("inf")
6    best_route = None
7
8    for order in permutations(cities):
9        route = (0,) + order + (0,)
10        cost = 0
11        for i in range(len(route) - 1):
12            cost += dist[route[i]][route[i + 1]]
13
14        if cost < best_cost:
15            best_cost = cost
16            best_route = route
17
18    return best_route, best_cost
19
20matrix = [
21    [0, 10, 15, 20],
22    [10, 0, 35, 25],
23    [15, 35, 0, 30],
24    [20, 25, 30, 0],
25]
26
27print(brute_force_tsp(matrix))

This exact version is useful for tiny instances because it guarantees the optimal answer. Past a certain point, though, the search space grows too fast. That is why practical solvers use dynamic programming, branch and bound, heuristics, or approximation algorithms instead of plain permutation search.

Common Pitfalls

• Mistaking any recursive algorithm for factorial time. Recursion is an implementation technique, not a complexity class.
• Forgetting that generating all permutations already costs n! before you do any extra work on each result.
• Using brute force on input sizes that look small but are already too large. 10 items is manageable in some cases, 15 usually is not.
• Confusing O(2^n) with O(n!). Both grow quickly, but factorial growth is much worse.
• Ignoring pruning opportunities. Many search problems can avoid examining every permutation if you cut off impossible or obviously bad branches.

Summary

• 'O(n!) usually appears when an algorithm must examine every ordering of n items.'
• Permutation generation is the simplest concrete example of factorial time.
• Brute-force traveling salesperson search is another standard example.
• Factorial growth becomes infeasible very quickly, even for modest input sizes.
• When exact search is too expensive, look for dynamic programming, pruning, heuristics, or approximation methods.