Exponential Algorithms: O(n!)

Exponential algorithms have a time complexity of O(n!), where n is the input size. These algorithms are generally inefficient and impractical for large inputs because of their rapid growth rate. Of all the different Big O notation problems, these are often considered the least efficient, and should be avoided if possible. Sometimes it cannot be avoided however.

To give you an example of how fast a factorial problem grows in complexity, consider the factorial function (n!) is the product of all positive integers up to n.

Therefore, 5! = 5 × 4 × 3 × 2 × 1 = 120. So an algorithm for 5 data points for inputs would take 120 operations to execute. Adding a single data point would increase this to 720 operations.

O(n!) algorithms typically involve recursive function calls or nested loops that explore all possible permutations or combinations of the input data.

Examples of O(n!) Algorithms

1. Traveling Salesman Problem (TSP): Given a set of cities and their pair-wise distances, find the shortest possible tour that visits each city exactly once and returns to the starting city. The TSP has an O(n!) solution, as there are n! possible permutations of cities.
2. Generating Permutations: Write an algorithm to generate all possible permutations of a given set of elements. This can be done recursively, with each recursive call branching into n possible directions, resulting in O(n!) time complexity.
3. Brute-Force Sudoku Solvers: A naïve approach to solving Sudoku puzzles involves trying all possible values for each empty cell, recursively exploring all possible solutions. This approach has an O(n!) time complexity, where n is the number of empty cells.
4. Towers of Hanoi (or Shanghai- I’ve seen it both ways). – This is a classic puzzle problem that’s easy to understand but challenging to solve.

The Tower of Hanoi problem can be explained as:

Imagine you have:

1. Three rods (A, B, and C)
2. A set of disks of different sizes, stacked on rod A in descending order (largest disk at the bottom)

Your goal is to move the entire stack of disks to rod C, following these rules:

1. Only one disk can be moved at a time.
2. A disk can only be moved from the top of one rod to the top of another rod.
3. A larger disk can never be placed on top of a smaller disk.

Real-World Scenarios

While O(n!) algorithms are often impractical for large inputs, they can still be useful in specific scenarios:

1. Small Input Sizes: When dealing with small input sizes, O(n!) algorithms can be acceptable. For example, generating all permutations of a small set of elements might be feasible.
2. Specialized Hardware: In some cases, specialized hardware can be designed to efficiently solve O(n!) problems. For example, custom-built circuits for solving TSP instances.
3. Approximation Algorithms: Instead of solving the problem exactly, approximation algorithms can be used to find near-optimal solutions in a more efficient manner.

Exponential algorithms with a time complexity of O(n!) are generally inefficient and impractical for large inputs. However, they can still be useful in specific scenarios, such as small input sizes, specialized hardware, or approximation algorithms. Understanding the limitations and applications of O(n!) algorithms is essential for any computer science student or practitioner.

Exponential Algorithms: O(n!) was originally found on Access 2 Learn