software-engineer-blog logoSoftware Engineer Blog

Module 3 · Complexity and data structures

Unit 9 of 49

Unit 9 · Module 3 · Complexity and data structures

Big-O without the maths

Not "how fast" — how the cost grows when the input does.

Unit 9 of the free 49-unit computer-science course, in complexity and data structures. 1 topic to watch or read, 3 interview questions answered in full and a short self-check.

Watch or read

One topic makes up this unit. Take each one whichever way suits you, then answer the questions below.

Big-O explained without the maths

Your function ran in 40 milliseconds on your laptop. That number tells you almost nothing, because a stopwatch measures the trip you just took and Big-O predicts the road you are on. Here is what Big-O actually counts — growth, not time — taught with one Python function, real measured numbers, the hidden linear scan that turns 258 ms into 0.9 ms with one word, and the honest half nobody writes down: the crossover below which the worse complexity class wins on the clock, every time.

ReelRead

Interview questions this unit unlocks

Asked out loud, answered out loud. Read the answer, then say it in your own words.

What does Big-O actually tell you, and what does it hide?

It tells you how the cost grows as the input grows, with constants and lower-order terms deliberately thrown away. That is its value and its blind spot in the same sentence: it predicts that doubling the input roughly doubles an O(n) pass, and it says nothing about whether that pass takes a nanosecond or a network round trip. Big-O is a prediction about shape, not a measurement of time.

The honest version: O(n) with a memory-friendly access pattern routinely beats O(log n) that chases pointers, for every n you will actually see.

What is amortised complexity? Give a real example.

It is the average cost per operation across a long sequence, when one occasional operation is far more expensive than the rest. Appending to a dynamic array is the standard case: most appends are O(1), but when the array is full it allocates a bigger block and copies everything, which is O(n). Because the capacity doubles, that copy happens exponentially less often, and the cost spread over all appends is a constant.

The follow-up is why doubling rather than growing by a fixed amount: growing by a constant makes the copies linear in number, and the amortised cost becomes O(n).

Two algorithms are O(n log n) and O(n). Which do you ship?

Whichever one measures faster on the real input, and I would say so plainly. Complexity classes only settle the question once n is large enough for the growth to dominate the constants, and plenty of production inputs never get there. I would also ask what the worst case looks like, because an average-case win that degrades badly on adversarial input is a latency incident waiting for its trigger.

Naming the input size is what makes this answer credible. "For n under about a thousand I would benchmark both" beats any amount of asymptotic reasoning.

Self-check — 3 questions

Answer alone, at 2am, with no interviewer in the room.

Part of Everything You Need to Know About Computer Science.