O(2ⁿ) & O(n!): Algorithms to Avoid

Exponential growth destroys performance. O(2ⁿ) and O(n!) represent computational nightmares. Recognizing them early is a survival skill. They can turn a "five-second feature" into a server that never returns.

O(2ⁿ): Naive Fibonacci

Each call branches into two. Calls explode with depth.

func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2) // 2^n calls!
}

func main() {
    fmt.Println(fib(40)) // Takes forever!
}

The problem: fib(40) recomputes the same subproblems billions of times. There's no memory of past work.

Fix with Memoization (O(n))

Cache results. Each subproblem is solved once.

var memo = map[int]int{}

func fibMemo(n int) int {
    if val, ok := memo[n]; ok {
        return val
    }
    if n <= 1 {
        return n
    }
    memo[n] = fibMemo(n-1) + fibMemo(n-2)
    return memo[n]
}

Same algorithm shape, but the cache collapses the exponential tree into a linear walk. This is the heart of dynamic programming.

O(n!): Permutations

Generating all arrangements of n items: n × (n-1) × ... × 1.

func permute(nums []int) [][]int {
    var result [][]int
    permutation(nums, []int{}, &result)
    return result
}

func permutation(nums, path []int, result *[][]int) {
    if len(nums) == 0 {
        temp := make([]int, len(path))
        copy(temp, path)
        *result = append(*result, temp)
        return
    }
    for i, v := range nums {
        newNums := append(append(nums[:i], nums[i+1:]...), 0)
        newNums = newNums[:len(newNums)-1]
        permutation(newNums, append(path, v), result)
    }
}

The math is brutal:

• n=10 → 3.6 million permutations
• n=15 → 1.3 trillion, practically impossible
• n=20 → outlives the universe

When You Hit Exponential

If your algorithm is exponential or factorial, ask:

1. Can I memoize? Repeated subproblems → cache them.
2. Can I prune? Branch-and-bound, A*, alpha-beta pruning skip dead branches.
3. Do I actually need all results? Often "any valid" beats "all valid."
4. Is this NP-hard? Then accept an approximation algorithm.

Conclusion

Exponential and factorial complexity isn't theoretical. It shows up in naive recursion, brute-force search, and permutation problems. Recognize the shape, then apply memoization, pruning, or a better algorithm before it ships to production.

Next up: space complexity and the lesser-known Ω and Θ notations.