Table of Contents
Quadratic vs exponential vs factorials
Quadratic Complexity - O(n²)
Quadratic complexity means that the runtime grows proportionally to the square of the input size. For example:
- If n = 10, operations ≈ 100
- If n = 100, operations ≈ 10,000
- If n = 1000, operations ≈ 1,000,000
Common examples of O(n²) algorithms:
- Nested loops iterating over an array
- Bubble sort
- Selection sort
- Insertion sort
Exponential Complexity - O(2ⁿ)
Exponential complexity means the runtime doubles with each additional input element. For example:
- If n = 10, operations ≈ 1,024
- If n = 20, operations ≈ 1,048,576
- If n = 30, operations ≈ 1,073,741,824
Common examples of O(2ⁿ) algorithms:
- Recursive calculation of Fibonacci numbers
- Brute force solutions to the traveling salesman problem
- Finding all subsets of a set
Factorial Complexity - O(n!)
Factorial complexity means the runtime grows according to the factorial of the input size. For example:
- If n = 5, operations ≈ 120
- If n = 10, operations ≈ 3,628,800
- If n = 15, operations ≈ 1,307,674,368,000 😨
Common examples of O(n!) algorithms:
- Generating all possible permutations of n items
- Brute force solution to the traveling salesman problem (checking every possible route)
- Solving certain combinatorial problems exhaustively
Comparison
To understand how dramatically different these complexities are, consider this:
- At n = 5:
- O(n²) performs 25 operations
- O(2ⁿ) performs 32 operations
- O(n!) performs 120 operations
- At n = 10:
- O(n²) performs 100 operations
- O(2ⁿ) performs 1,024 operations
- O(n!) performs 3,628,800 operations
- At n = 15:
- O(n²) performs 225 operations
- O(2ⁿ) performs 32,768 operations
- O(n!) performs over 1.3 trillion operations
Practical Implications
- O(n²) algorithms can be practical for small to medium-sized inputs
- O(2ⁿ) algorithms are typically only practical for very small inputs (usually n < 20)
- O(n!) algorithms are only practical for extremely small inputs (usually n < 10)
- When possible, factorial algorithms should be avoided in favor of more efficient alternatives
- The growth rate from fastest to slowest is: O(n²) < O(2ⁿ) < O(n!)
haochen xu