Factorial Time Complexity

Factorial time complexity refers to algorithms where the number of operations grows as the factorial of the input size. The factorial of a number ( n ) is defined as:

n! = n×(n−1)×(n−2)×…×2×1

This type of time complexity is extremely inefficient for large inputs, as the number of operations increases super-exponentially. Algorithms with O(n!) complexity are generally impractical for inputs larger than a very small size.

Example

The Traveling Salesman Problem (TSP)

Let's consider the Traveling Salesman Problem (TSP) as an example of an algorithm with O(n!) complexity.

Problem Statement:
Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the starting city.

How the Brute Force Solution Works:

1. Suppose you have 4 cities: A, B, C, and D.
2. The brute force approach involves trying every possible route to find the shortest one.
3. For 4 cities, the possible routes are:
   • A → B → C → D → A
   • A → B → D → C → A
   • A → C → B → D → A
   • A → C → D → B → A
   • A → D → B → C → A
   • A → D → C → B → A
4. There are 4! = 24 possible routes to check.

As the number of cities increases, the number of possible routes grows factorially:

• For 5 cities: ( 5! = 120 ) routes
• For 6 cities: ( 6! = 720 ) routes
• For 10 cities: ( 10! = 3,628,800 ) routes

This quickly becomes impractical to solve with brute force as ( n ) increases.

Why is TSP O(n!)?

• The brute force approach requires checking every possible permutation of cities to find the shortest route.
• For ( n ) cities, there are ( n! ) permutations.
• Therefore, the time complexity is O(n!).

Real-Life Analogy

Imagine you're hosting a dinner party and want to arrange 6 guests in different seating orders. To try every possible arrangement:

1. You start with 6 options for the first seat.
2. After choosing the first seat, there are 5 options left for the second seat.
3. Then 4 options for the third seat, and so on.

The total number of seating arrangements would be:

6! = 6×5×4×3×2×1 = 720

If you had 10 guests, the number of arrangements would jump to 3,628,800, making it practically impossible to try every possible seating order manually.

Optimization Tip:

For problems like TSP, where the brute force solution is O(n!), more efficient algorithms like Dynamic Programming (e.g., the Held-Karp algorithm) or heuristic approaches are used to find approximate solutions in a reasonable time.