Cost before code

A script that worked on the sample

A script has to compare a bank's settlement file with your own ledger and list every line where the two disagree. The script is short. For each line in the bank's file, it walks through the ledger from the top until it finds the line with the same reference number. On a sample of 2,000 lines from each side it finishes in 0.4 seconds with the right output, so it ships.

The real file has 1,000,000 bank lines, and the ledger is just as long. Both inputs are 500 times bigger than the sample, so a first guess is that the run takes a few minutes. Sixteen minutes in, the progress bar has moved one percent.

Work out the numbers before reading on. Each bank line may walk through the whole ledger. On the sample, that is 2,000 walks of up to 2,000 steps each. On the real file, it is 1,000,000 walks of up to 1,000,000 steps each.

Pause and predict The sample took 0.4 seconds. Both files are now 500 times longer. Roughly how long will the full run take?

How cost grows with the input

An interviewer asks "what does it cost?" after every solution. The answer they want is how the number of basic steps grows as the input grows. The number of seconds depends on the machine, but the way the step count grows does not.

Big-O notation keeps only the fastest-growing term and drops constant factors. For example, 3n² + 10n + 7 is O(n²): once n is large enough, the whole expression stays below 4n², because the 10n and the 7 grow much more slowly than n².

The settlement script follows this rule. The walk through the ledger runs once per bank line, which is n times, and one walk costs up to n steps, so the total is up to n × n steps.

Loops

One loop over n items runs its body n times, so it costs O(n). Two loops that run one after the other add their costs: n + n is 2n, which is still O(n).

A loop inside a loop multiplies: n outer steps, each running n inner steps, make n × n = n² steps.

Pause and predict In for i in range(n): for j in range(i), the inner loop runs only up to i instead of up to n. Does that change the big-O class of the code?

If each step halves what is left, then after k steps n / 2ᵏ remains. The loop stops when that reaches 1, so 2ᵏ = n and k = log₂ n. That is why binary search is O(log n), and why a counter that doubles from 1 up to n runs log₂ n times.

Recursion

To find the cost of a recursive function, draw its calls as a tree, with one node per call. The cost is the work done at each node, added up over all the nodes. Two trees are worth knowing well:

• Merge sort. Each call splits its range in half, so the tree is log₂ n levels deep. The ranges at one depth do not overlap and together cover the whole array, so the merges at each depth handle n elements in total. With log₂ n depths, the total is n log n.
• Plain recursive Fibonacci. Each call makes two more calls, and the argument shrinks by only 1 or 2, so the tree has about 1.618ⁿ nodes. But there are only n + 1 different arguments, so most of those calls repeat work. If you store each answer the first time you compute it, every later call with the same argument returns at once, and only about n calls do real work. That is the idea behind dynamic programming.

Sorting has a floor

A sort that learns about the elements only by comparing them needs about n log₂ n comparisons. Here is why. The input could be in any of n! possible orders, and the sort has to tell them all apart. Each comparison has two outcomes, so k comparisons can tell apart at most 2ᵏ orders. You need 2ᵏ ≥ n!, so k ≥ log₂(n!), which is about n log₂ n. So when a solution starts by sorting, that step costs O(n log n) and has to be counted.

Hash maps: O(1) on average

A hash map lookup is O(1) on average, provided the hash function spreads the keys evenly over the buckets. If every key lands in the same bucket, a lookup has to scan all n keys in it, which is O(n). In an interview, say "O(1) on average". Java 8 and later turn a crowded bucket into a tree, so the worst case there is O(log n).

Space, including the stack

The space a solution uses is the memory it allocates that grows with n, plus the largest size the call stack reaches. A recursive depth-first search may allocate no arrays at all, but every call that has not returned yet keeps a frame on the stack. On a path of n nodes that is n frames, O(n); on a balanced tree it is about log n frames. Python stops at about 1,000 nested calls by default, and Java running in the browser stops at a few thousand.

Amortised: one expensive step, paid for by many cheap ones

A dynamic array (a Java ArrayList or a Python list) doubles its capacity when it is full and copies every element into the new space. So a single append can cost O(n).

Pause and predict A single append can cost O(n). What do n appends, starting from an empty array, cost in total?

From the constraints to the budget

An online judge runs roughly 10⁸ simple steps a second in Java or C++, and about 10⁷ in Python, usually with a limit of a second or two. So the input size in the constraints tells you which costs are allowed before you design anything.

Pause and predict The constraints say n ≤ 10⁵ and the time limit is about one second. Which is the slowest of these costs that will still finish in time?

The same arithmetic, with real constants, sizes whole systems: System design: numbers to know. And it is why a transformer's cost grows with the square of the context: LLM: attention.

How to recognise it

You will ask what a solution costs in every unit after this one. The thing to watch for is a loop hidden inside a single line.

Pause and predict In Python, consider for x in items: if x in seen_list: ..., where seen_list grows until it holds n items. There is only one visible loop. What does the code cost?

What big-O leaves out

• How long one step takes. Big-O only says how the cost grows. An O(n) loop with an expensive body can be slower than an O(n log n) sort when n is small.
• The difference between average and amortised. A hash map is O(1) on average over typical inputs, and a badly chosen input can make it slow. An amortised O(1) append holds for every sequence of appends, whatever the input.
• Memory you did not allocate yourself. The recursion stack, the output, and the copies made by slicing all count as space, unless the problem says the output does not count.

Where it bites

• Assuming that two loops cost n². They do only when one loop is inside the other. When one runs after the other, their costs add.
• Forgetting the call stack. A recursive function does not use O(1) space. Count the longest chain of calls that are waiting at the same time.
• Missing a loop hidden in one line. x in list, list.index, remove(0), pop(0), slicing and substring each walk through or copy up to n elements.
• Calling a hash map O(1) without saying "on average". If the interviewer asks about the worst case, the answer is O(n) per operation.
• Dropping one of the sizes. Two inputs have two sizes. Merging lists of length m and n is O(m + n); calling it O(n) hides m.

Pause and predict A loop builds a string of n characters by running s += c once per character. What does the whole loop cost?