Big-O Thinking, Explained

Big-O describes how the work of an algorithm scales as the input size grows. It's the habit of asking, before you commit to an approach:

If the input doubles, does the work stay roughly the same, roughly double, or grow much faster than that?

That question tells you whether an approach will hold under the stated constraints.

The curves that matter in practice

A short vocabulary you can state clearly is enough:

Growth	Rough meaning	Everyday picture
O(1)	Constant	Open one known drawer
O(log n)	Halves each step	Binary search — cut the search space in half
O(n)	Linear	Touch each item once
O(n log n)	Sort-class	Typical comparison sorts (mergesort, heapsort)
O(n²)	Nested linear	For each item, scan the others
O(2ⁿ)	Exponential	Enumerate every subset — workable only for very small `n`

Spoken shorthand: “linear” means O(n), “quadratic” means O(n²), “logarithmic” means O(log n).

Growth curves — work vs input size

Each line is a familiar algorithm family. Watch how relative work climbs as n grows. Toggle curves; play to animate.

n = 1

O(n) — Single pass · touch each item oncework ≈ 1.0
O(n log n) — Mergesort · split, sort, mergework ≈ 0.0
O(n²) — Insertion sort · nested walk of the prefixwork ≈ 1.0

Three rules of thumb

1. Drop constants.
3n and n are the same family: O(n). Big-O tracks the shape of growth; constant factors are omitted.

2. Keep the dominant term.
n² + 100n + 50 is O(n²). For large n, the square term dominates the runtime.

3. Nested loops usually multiply.
One loop over n is O(n). A loop inside a loop over the same n is often O(n²) — unless you shrink the search space (binary search, early exits, hashing).

When you quote a cost, say average vs worst case when they differ. A hash map lookup is average O(1) and worst O(n) if every key collides.

Try it: Sort Timing Race

Suppose you need to put n numbers in order. Three approaches illustrate the same idea:

Insertion sort — for each new number, walk the sorted prefix to find its place → about O(n²) comparisons in the worst case.
Mergesort — split, sort halves, merge → O(n log n).
Counting sort (when values sit in a small range 0…k) — tally frequencies, then emit → O(n + k), often effectively linear when k is modest.

At n = 10, all three can feel instantaneous. At n = 1_000_000, insertion sort and mergesort diverge sharply. Counting sort only stays competitive while k remains small; if k is huge, the + k term becomes the bottleneck.

That is Big-O thinking: compare growth rates across input sizes.

n ≈ 10        → growth differences are hard to see
n ≈ 10³       → O(n²) starts to hurt
n ≈ 10⁶       → O(n²) often times out; O(n log n) usually still finishes

How to say it in live coding

When you choose an approach, state the cost briefly:

“I’ll keep a hash of what I’ve seen — one pass, average O(n) time and O(n) space. A nested scan would be O(n²).”

That covers the structure, the time and space bounds, and the alternative you considered.

The skill to build: read the loops (and recursion), name the growth family before you implement, and pick the shallower curve that still solves the problem.

Moves

Count the loops. Nested usually multiplies.
Drop constants. 3n and n are the same family.
Keep the dominant term. n² + n is O(n²).
Name the curve. 1, log n, n, n log n, n², 2ⁿ.
Compare at scale. Which wins when n is large?

Reach for it when

You need to justify a solution’s cost, choose between approaches, or explain why a correct solution fails under larger performance constraints.