Big-O Thinking, Explained

Big-O is a way to talk about how much work an algorithm does as the input gets bigger — not how many milliseconds it took on your laptop today.

Why “it feels fast” is not enough

On a Codility screen or a live coding round, a solution that passes n = 100 can still time out at n = 100_000. The machine is not being mean. You picked a curve that grows too steeply.

Big-O thinking is the habit of asking, before you type:

If the input doubles, does my work roughly stay the same, double, or explode?

That question separates “clever for a demo” from “safe under the time limit.”

The curves you actually need

You do not need a proof course. You need a small vocabulary you can say out loud:

Interview English: “This is linear” means O(n). “Quadratic” means O(n²). “Logarithmic” means O(log n).

The three rules that keep you honest

1. Drop constants.
3n and n are the same family: O(n). Big-O cares about shape, not the exact multiplier.

2. Keep the dominant term.
n² + 100n + 50 is O(n²). When n is large, the square term owns 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 cut the search space (binary search, early exits, hashing).

Average vs worst case matters when you say it: a hash map is average O(1) lookup, worst O(n) if everything collides. Say which one you mean.

Try it: Sort Timing Race

Imagine you must put n numbers in order. Three approaches show up in the same race:

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

At n = 10, they all feel instant. At n = 1_000_000, insertion sort is a different sport from mergesort. Counting sort wins only if k stays small; if k is huge, that “linear” plan is a trap.

That is Big-O thinking: race the curves, not the stopwatch on a toy input.

n ≈ 10        → curves barely matter
n ≈ 10³       → O(n²) starts to ache
n ≈ 10⁶       → O(n²) often dies; O(n log n) still breathes

How to use this in a screen

When you pick an approach, narrate the cost in one breath:

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

That sentence does three jobs: names the structure, states time and space, and shows you rejected the naive curve on purpose.

The skill to build: looking at loops (and recursion) and naming the growth family before you commit — then choosing the shallower curve that still solves the problem.

Moves

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

Reach for it when

You must justify a solution’s cost, pick between approaches, or explain why “works on my laptop” fails the performance tests.