Introduction

Permutation algorithms are a good example of a problem where output size dominates complexity. If an algorithm must generate every ordering of n distinct elements, it cannot avoid producing n! results. That fact sets the baseline for the time analysis before you even look at implementation details.

Start with the Number of Results

For n distinct items, the number of permutations is n!.

Examples:

• '3! = 6'
• '4! = 24'
• '5! = 120'
• '10! = 3,628,800'

This matters because any algorithm that actually outputs all permutations must spend at least some time per permutation. So there is already a lower bound of roughly Omega(n!) on the problem just from the number of results.

That is the first key insight: if the output itself is factorial in size, no clever implementation can make full permutation generation polynomial-time.

Why Many Analyses Use O(n! * n)

A permutation is not a single scalar value. It is typically a full arrangement of n elements. If your algorithm copies or prints all n elements for each of the n! results, the total work is often better described as O(n! * n).

A simple Python backtracking implementation shows why:

1def permute(items, path, used, result):
2    if len(path) == len(items):
3        result.append(path[:])
4        return
5
6    for i in range(len(items)):
7        if used[i]:
8            continue
9        used[i] = True
10        path.append(items[i])
11        permute(items, path, used, result)
12        path.pop()
13        used[i] = False
14
15
16values = [1, 2, 3]
17result = []
18permute(values, [], [False] * len(values), result)
19print(result)

The recursion explores all n! arrangements, and every time a complete permutation is found, path[:] copies n elements. That is why O(n! * n) is the practical time bound for this common style of algorithm.

The Difference Between Search Work and Output Work

Sometimes people describe permutation generation as O(n!), and sometimes as O(n! * n). Both appear in discussions because they emphasize different costs.

• 'O(n!) highlights the number of leaf results'
• 'O(n! * n) includes the cost of materializing each length-n permutation'

For most practical code, O(n! * n) is the more informative answer because real programs usually need to store, print, or pass around each generated arrangement.

Space Complexity Depends on What You Store

The space cost also depends on the design.

If you generate permutations one at a time and process them immediately, auxiliary space can be relatively small, often around O(n) for the recursion stack and bookkeeping.

If you store every permutation, space becomes much larger because you are storing n! arrays of length n.

A generator-style approach avoids that full storage cost:

1def permute_generator(items, path, used):
2    if len(path) == len(items):
3        yield path[:]
4        return
5
6    for i in range(len(items)):
7        if used[i]:
8            continue
9        used[i] = True
10        path.append(items[i])
11        yield from permute_generator(items, path, used)
12        path.pop()
13        used[i] = False
14
15
16for p in permute_generator([1, 2, 3], [], [False] * 3):
17    print(p)

This still takes factorial time, but it does not keep the entire result set in memory.

Different Algorithms, Same Fundamental Growth

Heap's algorithm, recursive backtracking, lexicographic next-permutation methods, and iterative swap-based approaches can differ in constants and memory usage, but they all face the same factorial output size if they enumerate every permutation.

That means the high-level complexity class is not where these algorithms differ most. The interesting differences are usually:

• how much auxiliary memory they need
• whether they generate in place
• whether they are easy to stream lazily
• how much copying they perform per permutation

So if two permutation generators both produce all permutations, Big O alone rarely picks a clear winner.

When the Analysis Changes

If the algorithm does not generate all permutations, the analysis can be very different.

For example:

• generating one random permutation can be O(n) with Fisher-Yates shuffle
• checking whether any permutation satisfies a property may allow pruning
• counting permutations without listing them can be much cheaper than enumerating them

That is why it is important to distinguish "permutation problem" from "full permutation generation." The factorial cost is tied to enumeration of all results.

A Small Reality Check

The growth becomes impractical quickly. Even if each generated permutation were processed extremely fast, n! rises too sharply for large n.

That means performance discussions about permutation algorithms are often really discussions about problem framing:

• do you truly need every arrangement
• can you sample instead
• can you prune the search space
• can you solve the task without explicit enumeration

Those questions matter more than micro-optimizing the recursion.

Common Pitfalls

The most common mistake is answering O(n) or O(n^2) just by looking at the visible loops inside one recursion frame and ignoring the total number of generated permutations. Another is saying only O(n!) without considering that materializing each permutation usually costs O(n) work as well. Developers also often ignore the space difference between yielding permutations one at a time and storing the whole result set. A final issue is discussing permutation algorithms as if they were slow because of poor implementation rather than because the output size itself is factorial.

Summary

• Any algorithm that generates all permutations must deal with n! results.
• In practical implementations, time is often best described as O(n! * n) because each permutation has n elements.
• Generator-style code can keep auxiliary space much smaller than storing all permutations.
• Different permutation algorithms vary in constants and memory behavior, but not in the fundamental factorial growth.
• Before optimizing the algorithm, ask whether you really need to enumerate every permutation at all.