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 — the good sorts (merge, Timsort). The realistic ceiling for "process everything, smartly."
O(n²) quadratic — nested loops, naive sorts, all-pairs. Fine for hundreds, painful for millions.
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

For everyday data, O(n log n) and below is "sleeps fine at night." O(n²) is "okay until the data grows." Anything exponential — O(2ⁿ), O(n!) — is a fire alarm: it works on your tiny test case and detonates on real input. A huge part of algorithm design (especially the Dynamic Programming track) is dragging an exponential brute force down to a polynomial that actually ships.

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