The Complexity Zoo, From O(1) to O(n!)

"There are maybe eight complexities you meet in real life. Learn the ladder once and you can place almost any algorithm on it at a glance."

The Ladder, Best to Worst

Ranked from "barely notices the input" to "dies if you sneeze at it":

O(1) constant — dict lookup, array index, append to a list. The dream. Input size is irrelevant.
O(log n) logarithmic — binary search, balanced-tree lookup. Halving each step. A billion items in ~30 steps.
O(n) linear — scan a list, find a max. Touch each item once. Honest and fine.
O(n log n) linearithmic — merge sort, Timsort, and the workhorse rung for processing large inputs intelligently. This is where serious general-purpose sorting lives.
O(n²) quadratic — nested loops, naive sorts, all-pairs. Hundreds can be fine; millions are brutal. Check the actual input limit, but hear the alarm.
O(n³) cubic — naive matrix multiply, triple-nested loops. Already rough at a few thousand.
O(2ⁿ) exponential — try every subset, naive recursive Fibonacci. Dies around n = 40.
O(n!) factorial — try every ordering, brute-force traveling salesman. Dies around n = 12.

Make the Gulf Visceral

The names hide how violent the differences are. At n = 50: O(n) is 50 operations, O(n²) is 2,500, O(2ⁿ) is about a quadrillion, and O(n!) is a number with 65 digits — more than the atoms in the observable universe. Same input. The algorithm's shape is the difference between "instant" and "the heat death of the universe finishes first." Run the code below and watch the numbers explode.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!). Memorize this ladder. Knowing which rung you're on tells you instantly whether your input size is safe.

The Line You Don't Want to Cross

Constants, hardware, and latency limits set the exact boundary, but the ladder's alarm is still vivid. For everyday data, O(n log n) and below is usually "sleeps fine at night," while O(n²) is "fine until the data grows." O(2ⁿ) and O(n!) are fire alarms: they smile on tiny tests and detonate on real input. A huge part of algorithm design—especially the next Dynamic Programming track—is dragging exponential brute force down to a smaller state space or a polynomial-time method that can actually ship.

Pippa's Confession

I wrote a "try every combination" solution once that flew through my 10-item test and then sat there, fan screaming, on the real 45-item input. I'd built an O(2ⁿ) and 2⁴⁵ is 35 trillion. Dad didn't even debug it — he just looked at the shape and said "that's exponential, it's not slow, it's impossible." Recognizing the rung saved me from optimizing something that never could have finished.

Code

Watch the numbers explode·python

import math

# How many operations each complexity needs, for growing n.
# Watch where the numbers stop being numbers you can imagine.
shapes = {
    "O(1)":      lambda n: 1,
    "O(log n)":  lambda n: max(1, int(math.log2(n))),
    "O(n)":      lambda n: n,
    "O(n log n)":lambda n: int(n * math.log2(n)),
    "O(n^2)":    lambda n: n * n,
    "O(2^n)":    lambda n: 2 ** n if n <= 60 else float('inf'),
    "O(n!)":     lambda n: math.factorial(n) if n <= 20 else float('inf'),
}

for n in (10, 20, 50):
    print(f"\n--- n = {n} ---")
    for name, f in shapes.items():
        print(f"  {name:<11}: {f(n):,}" if f(n) != float('inf') else f"  {name:<11}: astronomically huge")

# O(n) at n=50 is 50. O(n!) at n=50 has 65 digits.
# Same input. The shape is everything.

Exercise

Place each on the ladder: (1) looking up a contact by name in a hash map, (2) sorting a playlist, (3) generating every possible seating arrangement for n dinner guests, (4) binary-searching a sorted array. Then: which one becomes impossible fastest as n grows, and why?

Hint

Hash lookup is the dream rung; sorting is the realistic ceiling; 'every arrangement' is permutations. The factorial one detonates first — n! outruns even 2ⁿ.

The Ladder, Best to Worst

Make the Gulf Visceral

The Line You Don't Want to Cross

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0