Factorial (O(n!))

At a glance: The number of possible arrangements grows as the product 1 × 2 × ... × n.

Jump to: Time complexity · Space complexity · Try it yourself

Understand the growth

To arrange n distinct objects, there are n choices for the first position, n-1 for the second, then one fewer for each remaining position. Multiplying these possibilities yields n! complete permutations.

Going from n to n + 1 multiplies the permutation count by n + 1. Thus the ratio is not a fixed constant as with 2ⁿ; it becomes larger as n increases. Factorial growth eventually dominates any fixed-base exponential.

Why arrangements multiply factorially

To arrange n distinct items in order, choose one of n items for position 1, then one of n-1 remaining items for position 2, and continue until one choice remains. Multiplying the counts yields n! = n × (n-1) × ... × 1. Going from n to n+1 items multiplies the number of arrangements by n+1, a factor that itself keeps growing.

This is stronger growth than fixed-base exponential counting. Five items have 120 permutations, eight have 40,320, and ten have 3,628,800. The rapid increase explains why enumerating candidate orders is usually limited to small inputs. Such enumeration appears in brute-force traveling-salesperson tours, scheduling orders, and all-permutation test generation.

However, counting the number of arrangements mathematically does not require visiting them one by one. An algorithm may compute n! with a short loop (ignoring large-integer arithmetic costs), even though generating every permutation necessarily creates an enormous amount of work.

Worked example

There are 120 permutations for five distinct objects, 720 for six, 5,040 for seven and 40,320 for eight. Adding just three items to a five-item problem raises the number of arrangements by a factor of 336.

Walk through three permutations levels

Start with [A, B, C]. At the first position, choose A, B or C. For each choice, only two options remain for the second position, then one for the third. The leaves are ABC, ACB, BAC, BCA, CAB and CBA: 3 × 2 × 1 = 6 arrangements.

Adding D produces 4 × 6 = 24 arrangements. Adding E produces 5 × 24 = 120. A naive brute-force solver that evaluates every order will therefore perform at least that many candidate evaluations, before accounting for the time taken to score or copy each order. Keeping the permutation in one mutable array is more memory-efficient than storing every generated order.

Time complexity

Representative time example: Enumerating permutations.

The in-place swap-and-recurse example chooses one value for each position until it reaches a full permutation. It visits n! leaves. If ProcessPermutation performs constant work, its traversal can be classified Θ(n!) under the stated model. If processing needs to print or copy all n positions, the output work becomes Θ(n·n!). The usual input to this procedure is an array of distinct elements; duplicates produce repeated arrangements unless explicitly handled.

Distinguish visiting from processing permutations

The in-place swap-and-recurse implementation explores one branch for each remaining candidate at each position. Its recursion tree has n! leaves, and Θ(n!) internal-node/swap work for n at least two when a leaf callback costs O(1). If ProcessPermutation examines all n positions or copies each permutation, the total becomes Θ(n·n!). Printing every full permutation also incurs Ω(n·n!) output work.

The routine includes a swap to select a candidate and a swap back to restore the array. Without the swap back, future branches would start from modified state and the enumeration could become incorrect. A solver that exits after the first acceptable arrangement may be faster on favorable inputs, but an exhaustive worst-case analysis still covers all candidates.

C#

C# | Factorial.cs

void Permute(int pos, int[] a)
{
    if (pos == a.Length) { ProcessPermutation(a); return; }
    for (int i = pos; i < a.Length; i++)
    {
        (a[pos], a[i]) = (a[i], a[pos]);
        Permute(pos + 1, a);
        (a[pos], a[i]) = (a[i], a[pos]);
    }
}

C++

C++ | factorial.cpp

#include <vector>
#include <utility>

void permute(int pos, std::vector<int>& a) {
    if (pos == static_cast<int>(a.size())) { processPermutation(a); return; }
    for (int i = pos; i < static_cast<int>(a.size()); ++i) {
        std::swap(a[pos], a[i]);
        permute(pos + 1, a);
        std::swap(a[pos], a[i]);
    }
}

Analysis: In-place permutation generation visits n! leaves. This recursive routine visits n! leaves, and performs Θ(n!) loop/swap work when ProcessPermutation is O(1). If processing or copying each full permutation takes Θ(n), overall time becomes Θ(n·n!).

The C++ version illustrates the same operation. The container, compiler and any functions called by the example still matter when analyzing a complete program.

Space complexity

Representative memory example: Storing one marker per permutation.

An in-place generator can reuse the input array and keep at most n recursive frames, so it needs O(n) auxiliary stack space. Storing one constant-size marker for each permutation requires Θ(n!) cells, while storing every complete length-n permutation requires Θ(n·n!) element cells. Allocating one byte per permutation illustrates the class O(n!) space; it is not the memory used by the in-place generator.

In-place search avoids factorial storage

An in-place generator stores the current n-element arrangement and at most n+1 call frames. Excluding the input array, its auxiliary stack memory is Θ(n); including the current arrangement gives Θ(n) storage as well. It does not need to keep all previously visited permutations. In contrast, storing one fixed-size flag per permutation uses Θ(n!) memory.

If every actual permutation is copied into an array of length n, the stored element count is Θ(n·n!), even if each copy is compressed or decorated differently. A collection of permutation indices can reduce the constant factor but not remove the number of results. For large n, even storing one byte per permutation quickly becomes impractical; 10! already exceeds three million entries.

C#

C# | Factorial.cs

// Allocate one byte of metadata per permutation.
// For sufficiently small n only:
byte[] flags = new byte[Factorial(n)];

C++

C++ | factorial.cpp

#include <vector>
#include <cstdint>

// One byte per permutation illustrates O(n!) space (small n only).
std::vector<std::uint8_t> flags(factorial(n));

Analysis: A collection of n! constant-size results uses Θ(n!) memory; storing every full length-n permutation takes Θ(n·n!). In-place generation requires only O(n) call stack.

The stated bound describes stored elements and active call frames. Actual byte counts also depend on runtime, allocator and element representation.

Factorial enumeration is a deliberate choice

Factorial work is justified when the task truly requires listing every distinct arrangement, but often unnecessary when the goal is to find one good ordering. Before brute forcing, ask whether dynamic programming, greedy rules, branch-and-bound, or domain constraints avoid most possibilities. A graph-tour problem may have symmetries that reduce duplicate tours, although removing a constant or polynomial factor does not automatically make exhaustive search tractable.

Do not label every recursive scheduling solution O(n!) merely because ordering is involved. Some recurrences revisit repeated states, some prune aggressively, and some compute a count directly. Derive the actual state space and per-state work. Also remember that repeated or indistinguishable input items reduce the number of distinct permutations compared with n! for unique items.

Practical example: ordering a sequence of deliveries

Suppose a dispatch game gives a vehicle eight distinct stops. Trying every order means evaluating 8! = 40,320 routes before even accounting for route-length calculations. With ten stops the candidate count grows to 10! = 3,628,800. If a route evaluation sums ten edge lengths, that adds a factor proportional to the route length, so the full brute-force runtime is larger than the permutation count alone.

For small instances, exhaustive enumeration can be valuable as a correctness reference for a faster heuristic. For larger instances, dynamic programming, branch-and-bound or approximation methods may be more suitable. Simply using recursion does not make a route solver factorial: derive its actual branching pattern, pruning rules and per-candidate work.

Common mistake

Watch out: Distinguish enumerating permutations, counting them mathematically, and searching for one satisfactory permutation. The fact that n! arrangements exist does not automatically mean every problem must visit all of them.

Try it yourself

List the six permutations of three distinct values. Compare how many arrangements exist for six and seven values, then decide whether you need to store all results.

1. Define exactly what n represents.
2. Count the key operation in the best and worst case where relevant.
3. Count the maximum simultaneously live memory.
4. Check your prediction in the Big O explorer.

Continue learning

Big O overview · Time complexity · Space complexity · Compare classes