Foundations

Big-O notation

Measuring cost by how it grows, not by seconds

~12 minLesson 2 of 25Written by Claude Opus 4.8

If you measure an algorithm in seconds, you're really measuring your laptop. Big-O throws away hardware, language, and constant factors and keeps the one thing that survives all of them: how does the work grow as the input grows? Double the input - does the work stay flat, double, or explode?

The core question

Big-O answers: "as the input size $n$ heads toward infinity, what shape does the cost curve take?" An O(1) algorithm doesn't care how big

n

is. An O(n²) algorithm does four times the work when you double

n

. That difference decides whether your program finishes in a blink or in a week.

Watch the curves race

Drag the slider to grow the input size $n$ . Each curve is a complexity class; the readout shows exactly how many operations each one costs at your chosen $n$ . Push $n$ up and watch the classes fan apart - the whole story of Big-O is in that fan.

Growth-rate racetrack. Drag the input size n and watch the six complexity classes fan apart; toggle the log y-scale so the exponential stops clipping.

O(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)

input size n = 8log y-scale

class	operations at n = 8
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64
O(2ⁿ)	256

The gap is everything

n

= 40, O(1) still costs 1 operation while O(2ⁿ) costs over a trillion. Same input, a trillion-fold difference in work - purely from the shape of the algorithm. That's why we obsess over complexity classes and barely mention clock speed.

The classes you'll meet, best to worst

Class	Name	Doubling n means...	Typical example
O(1)	constant	no change	array index, hash lookup
O(log n)	logarithmic	+1 step	binary search
O(n)	linear	doubles	scan a list
O(n log n)	linearithmic	a bit more than doubles	merge sort, quicksort
O(n²)	quadratic	×4	nested loops, bubble sort
O(2ⁿ)	exponential	squares (!)	brute-force subsets

The two simplification rules

Big-O deliberately blurs detail. Two rules do the blurring:

Drop constant factors. $3 n$ and $100 n$ are both O(n) - because as $n$ grows, the constant stops mattering to the shape.
Keep only the dominant term. $n^{2} + 5 n + 9$ is O(n²) - the $n^{2}$ term eventually dwarfs the rest.

The formal definition (it's friendlier than it looks)

We say

f (n) = O (g (n))

when

g

is an upper bound on the growth of

f

- precisely, if there exist constants

c > 0

and

n_{0}

such that:

f (n) \leq c \cdot g (n) for all n \geq n_{0} .

In words: past some starting point

n_{0}

f

never grows faster than a constant multiple of

g

. That "past some point" is exactly why we drop constants and lower-order terms - they only matter for small

n

, and Big-O is a statement about large

n

# O(n): one pass
for x in items:            # runs n times
    print(x)

# O(n^2): a loop inside a loop
for x in items:            # n times ...
    for y in items:        # ... n times each = n*n
        compare(x, y)

Reading complexity off code: count the nested loops

Check yourself

A loop over n items, each iteration running another full loop over the same n items, is:

Under Big-O, the cost 6n² + 500n + 9999 simplifies to:

Recall: why do we drop the constant factor and the lower-order terms?

Try to state it, then check.

Lock it in

Big-O measures how an algorithm's cost grows with input size, not seconds on any one machine.
Two rules do the blurring: drop constant factors, keep only the dominant term.
The classes best to worst: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) - and the gap between them is everything.
Formally f(n) = O(g(n)) when f never exceeds a constant multiple of g past some n₀, which is why small-n detail is ignored.

Primary source

The MIT 6.006 lectures on asymptotic complexity give the rigorous treatment. Keep the Big-O Cheat Sheet open as a one-page lookup, and if the algebra of the definition feels heavy, Abdul Bari derives it slowly by hand.

Ask your teacher

Want the difference between Big-O, Big-Θ, and Big-Ω, or how "amortized" and "average-case" fit in? Ask and I'll build the follow-up. This idea powers a connection lesson later: why attention costs O(n²) in an LLM.