Skip to main content
Big O Notation
CHAPTER 13 Beginner

Factorial Complexity O(n!)

Updated: May 17, 2026
15 min read

# CHAPTER 13

Factorial Complexity O(n!)

1. Introduction

If Exponential $O(2^n)$ is the boundary of modern computing, Factorial Complexity $O(n!)$ is the abyss. It is the absolute, unquestionable worst Time Complexity that exists in computer science. In a Factorial algorithm, you are not doubling the workload. You are multiplying the workload by every descending integer of the input size. If $n = 5$, the operations are $5 \times 4 \times 3 \times 2 \times 1 = 120$. If $n = 10$, the operations are $10 \times 9 \times 8... = 3.6$ Million. If $n = 20$, the operations exceed the number of grains of sand on Earth.

2. Learning Objectives

By the end of this chapter, you will be able to:
  • Define mathematical Factorial Expansion ($n!$).
  • Understand what "Permutations" are and why they demand $O(n!)$.
  • Explain the legendary "Traveling Salesman Problem" (TSP).
  • Recognize why Factorial scale algorithms are deemed practically unsolvable.

3. The Mathematics of "Factorial"

The growth of $O(n!)$ is so violently aggressive that a standard graph cannot visually display it; the line shoots straight up into infinity almost immediately.
Input Size ($n$)$O(2^n)$ Exponential$O(n!)$ Factorial (Absolute Disaster)
532 ops120 ops
101,024 ops3.6 Million ops
1532,768 ops1.3 Trillion ops
201 Million ops2.4 Quintillion ops (Impossible)

Notice that at $N=20$, Exponential time takes 1 Million operations (a microsecond). Factorial time takes 2.4 Quintillion operations. No computer on earth can resolve an $O(n!)$ algorithm if the input surpasses 20.

4. The Trigger: Permutations

Why would anyone write an algorithm this slow? Because sometimes, math forces you to. The absolute guaranteed trigger for $O(n!)$ is generating Permutations. A permutation is every possible unique ordering of a set of items.

If you have 3 letters: [A, B, C]. How many unique combinations can you make?

  1. 1. ABC
  1. 2. ACB
  1. 3. BAC
  1. 4. BCA
  1. 5. CAB
  1. 6. CBA
Total = 6. (Math: $3 \times 2 \times 1 = 6$). If you have a password that is exactly 10 unique characters long, there are $10!$ (3.6 Million) possible combinations of those 10 letters.

5. The Ultimate Example: The Traveling Salesman Problem (TSP)

The most famous $O(n!)$ problem in the history of mathematics is the Traveling Salesman Problem. *Goal: A delivery driver has to drop off packages at 15 different cities. He must find the absolute shortest total driving route that visits every city exactly once and returns home.*

The Naive Brute Force approach: To guarantee the absolute shortest route, the computer must physically calculate *every single possible permutation* of driving paths, calculate their total mileage, and pick the smallest one. If there are 15 cities, there are $15!$ possible driving routes. The computer must calculate 1.3 Trillion routes. If a FedEx driver has to drop off 50 packages, $50!$ is a number so phenomenally large that it exceeds the atoms in the known universe.

6. Implementation in Code

Generating permutations requires highly complex branching recursion inside a loop.

#### Python Example: Generating Permutations

python
12345678910111213141516171819 
# O(n!) Time: The algorithm loops, and inside the loop, it recurses!
def generate_permutations(arr):
    if len(arr) == 1:
        return [arr]
    
    permutations = []
    
    # Iterate through every single element...
    for i in range(len(arr)):
        # Extract the current element
        current_item = arr[i]
        # Recursively map the remaining elements
        remaining_items = arr[:i] + arr[i+1:]
        
        # Branch the execution catastrophically!
        for p in generate_permutations(remaining_items):
            permutations.append([current_item] + p)
            
    return permutations

7. How do we solve the Unsolvable?

Since we cannot process $O(n!)$, how does Google Maps give us driving routes? How does FedEx deliver packages? They cheat. Enterprise engineering abandons the pursuit of the "Absolute Perfect" route. Instead, they use Heuristics and Greedy Algorithms. Google Maps does not calculate $15!$ combinations. It simply looks at the current city, selects the *closest* next city, and drives there. This Greedy approach executes in blindingly fast $O(n^2)$ time. It might result in a driving route that is 2% less efficient than absolute mathematical perfection, but it calculates in 10 milliseconds instead of 500 years.

8. Common Mistakes

  • Confusing Combinations ($2^n$) with Permutations ($n!$): A Combination asks: "Who is in the group?" (Order does not matter. [A,B] is the same as [B,A]). A Permutation asks: "How are they specifically ordered?" ([A,B] and [B,A] are totally distinct matrices). Permutations demand drastically more computational effort.

9. Exercises

  1. 1. If you add exactly 1 more city to a route that originally had 10 cities, exactly how many times does the algorithmic workload multiply?
  1. 2. Explain the fundamental difference between calculating $O(2^n)$ and calculating $O(n!)$.

10. MCQs with Answers

Question 1

What specific mathematical calculation geometrically represents the catastrophic expansion of $O(n!)$ Factorial Complexity?

Question 2

Within the realm of theoretical Computer Science, how is $O(n!)$ Factorial Time strictly categorized regarding hardware capabilities?

Question 3

Which algorithmic objective universally mandates the devastating geometric execution of an $O(n!)$ looping matrix?

Question 4

What legendary algorithmic logic puzzle physically demonstrates the paralyzing limitations of $O(n!)$ scaling regarding logistical route planning?

Question 5

When generating combinatorial recursive code evaluating $O(n!)$, what is the highly complex architectural syntax triggering the explosion?

Question 6

If an $O(n!)$ logistical algorithm maps 5 cities successfully, and the user suddenly injects exactly ONE additional city ($N=6$), what happens to the total processing load?

Question 7

How do massive logistics corporations (like FedEx or Amazon) successfully resolve route pathing without triggering apocalyptic $O(n!)$ server meltdowns?

Question 8

What defines the foundational geometric difference separating $O(2^n)$ Exponential Logic from $O(n!)$ Factorial Logic?

Question 9

When charting $O(n!)$ on a standard Asymptotic Graphical Axis evaluating Input Size vs Operations, how does the visual line manifest?

Q10. True or False: Because $O(n!)$ is so catastrophic, you will never be asked to write a permutation algorithm in a FAANG whiteboard interview. a) True. FAANG interviewers only ask for optimal $O(n)$ code. b) False. FAANG interviewers actively demand permutation code (like backtracking string generation) explicitly to test your ability to safely architect, bound, and control the recursive matrix without triggering Stack Overflows on small datasets. Answer: b) False. FAANG interviewers actively demand permutation code (like backtracking string generation)...

12. Interview Preparation

Top Interview Questions:
  • *Theoretical Limitation:* "Can we solve the Traveling Salesman Problem optimally using Dynamic Programming?" *(Answer: No! Even if you deploy extreme Bit Masking and DP Memoization (The Held-Karp algorithm), it merely reduces the complexity from $O(n!)$ down to $O(n^2 2^n)$. It is an improvement, but it is still catastrophically Exponential and structurally unsolvable for large datasets!)*

13. Summary

Factorial Complexity $O(n!)$ is the ultimate limit of computation. It forces software engineers to accept a humbling reality: computers are not omnipotent. When confronted with infinite permutations, we must abandon absolute mathematical perfection and instead engineer intelligent, efficient, heuristic approximations.

14. Next Chapter Recommendation

We have officially mapped the entire spectrum of Big O Notation, from the lightning speeds of $O(1)$ to the apocalyptic abyss of $O(n!)$. But until now, we have only discussed the "Upper Bound" (Worst Case). What about the Best Case? What about the Average Case? In Chapter 14: Big Omega and Big Theta Notation, we will introduce the complete mathematical trinity of algorithm bounding.

Finish this Chapter

Save your progress on your learning path and prepare for coding interview challenges.

Previous Chapter Exponential Complexity O(2ⁿ)
Next Chapter Big Omega and Big Theta Notation

Discussion

Join the discussion

Log in or create a free account to participate.

Sort: ·

Explore More

📖 Related Tutorials 4

❓ Related Quizzes 5