Big O Notation Explained Visually — A Practical Guide

Big-O notation is the vocabulary programmers use to talk about how algorithms scale — and it is routinely mis-taught as a scary math topic when it is really one simple question: when the input gets bigger, how much more work does the algorithm do? Not "how fast is it" — how fast does the cost *grow*.

That distinction is everything. An algorithm can be quick on 10 items and catastrophic on 10 million, and Big-O is the tool that predicts the catastrophe before you ship it. In this guide we will pin each common complexity class to a concrete algorithm you can actually watch run, so the curves stop being abstract.

What Big-O actually measures

Big-O describes the growth rate of an algorithm's cost as a function of input size n. It deliberately ignores two things: constant factors and lower-order terms. Suppose careful counting shows an algorithm performs exactly 3n² + 5n + 20 operations. Big-O throws away the 3, the 5n, and the 20 and calls it O(n²).

That feels like cheating until you see why it is justified. At n = 10 the discarded terms matter: 3n² is 300 and 5n + 20 is 70 — a fifth of the total. At n = 1,000 the n² term contributes 3,000,000 while 5n + 20 contributes 5,020 — less than 0.2%. As n grows, the fastest-growing term does not just win, it makes everything else a rounding error. And the constant 3? It shifts the curve up but never changes its *shape* — double the input and the work quadruples whether the constant is 3 or 300.

exact cost:  3n² + 5n + 20

n = 10       300 + 70        →  n² term is ~81% of the work
n = 100      30,000 + 520    →  ~98%
n = 1,000    3,000,000 + 5,020  →  ~99.8%

Big-O keeps the shape, drops the noise:  O(n²)

The five classes you actually meet

O(1) — constant time: hash table lookup

The cost does not depend on n at all. A hash table is the canonical example: to find a key, hash it, jump straight to that bucket, done. Whether the table holds 10 entries or 10 million, the lookup does the same handful of operations. Watch the visualizer and notice the algorithm never scans — it *computes* where to look.

O(log n) — logarithmic: binary search

Binary search checks the middle of a sorted array and throws away half the remaining elements — every single step. Halving is absurdly powerful: 1,000 elements need at most ~10 checks, and 1,000,000 need only ~20, because 2²⁰ is already past a million. Doubling the input adds one step. In the visualizer, watch the active range collapse toward the target; the run is over almost before it starts.

O(n) — linear: linear search

Linear search walks the array front to back until it finds the target. On average it inspects half the elements; in the worst case, all of them. Double the array, double the work — the cost grows in lockstep with n. This is the baseline class: any algorithm that must at least *look at* every input element is Ω(n), which is why summing an array or finding a maximum can never beat linear.

O(n log n) — linearithmic: merge sort

Merge sort splits the array in half recursively (log n levels of splitting) and does O(n) merge work at each level: n work × log n levels = O(n log n). This class is special because it is provably the best possible for comparison-based sorting — no algorithm that sorts by comparing pairs can beat it in the general case. In practice it behaves like "slightly heavier than linear": 1,000,000 elements cost about 20 million operations, not a million millions.

O(n²) — quadratic: bubble sort

Bubble sort compares every element against its neighbours across roughly n passes: n passes × n comparisons ≈ n². The tell-tale source-code signature is a loop nested inside a loop, both running over the input. Quadratic growth is brutal — double the input and the work quadruples. We walk through exactly where those n²/2 comparisons come from in How Bubble Sort Works.

The growth table: why the classes are different universes

These are mathematical operation counts (rounded), not benchmarks — and they are the entire argument for caring about Big-O:

Read the bottom row. At a million elements, binary search does 20 operations while linear search does a million — a 50,000× gap. Merge sort does 20 million while bubble sort does a trillion. If one operation takes a nanosecond, that is 20 milliseconds versus roughly 17 minutes. No compiler flag, no faster CPU, no amount of micro-optimization closes a gap like that — only a better algorithm does.

Best, average, and worst case

A single algorithm does not have one cost — it has a cost *distribution* over inputs. Linear search finds a target at index 0 in one step (best case), scans half the array on average, and scans everything when the target is missing (worst case). Quicksort is the famous example: O(n log n) on average but O(n²) on adversarial input — the entire subject of Quicksort vs Merge Sort.

By convention, an unqualified Big-O usually refers to the worst case, because it is the only number you can promise. But engineering decisions weigh all three: quicksort's terrible worst case is tolerated everywhere precisely because its *average* case is excellent and the worst case can be made astronomically unlikely.

Space complexity: the same idea, applied to memory

Big-O measures any resource that grows with input, and memory is the other one that matters. Bubble sort swaps elements inside the array it was given — O(1) extra space. Merge sort allocates an auxiliary array as large as the input — O(n) extra space. Recursive algorithms also pay for their call stack: binary search implemented recursively holds O(log n) frames.

Time and space frequently trade against each other. A hash table spends O(n) memory to buy O(1) lookups; searching the raw array spends no extra memory and pays O(n) time per search. Neither is "right" — Big-O just prices both sides of the deal.

Common mistakes

• "Lower Big-O is always faster." Only for large n. Big-O hides constants, and for small inputs constants dominate — which is why production sorts switch to insertion sort (O(n²)!) below a few dozen elements. The crossover point is real.
• "O(1) means fast." It means *constant*, not cheap. An operation that always takes 3 seconds is O(1). A hash lookup involving hashing and possible collision chains is O(1) but costs more than a couple of array reads.
• "O(n²) means it takes exactly n² steps." Big-O is a growth bound, not a step count. Bubble sort with an early-exit flag finishes sorted input in one O(n) pass and is still classed O(n²) by its worst case.
• "Big-O describes the code, full stop." It describes the code *on a stated case*. Always ask: best, average, or worst? For which operation? Amortized or per-call?
• Dropping n vs dropping n². You may only discard *lower-order* terms: 3n² + 5n is O(n²), never O(n). The dominant term is sacred.

See the curves, not the formulas

Big-O finally clicks when the classes stop being algebra and become shapes you have watched: the instant hash jump, binary search's collapsing window, the patient linear scan, merge sort's tidy halves, bubble sort's grinding passes. Pick two algorithms from different classes, run them on the same input, and the table above turns into something you can see.