Big-O reasoning and amortized analysis — every question, written out
Deriving bounds rather than reciting them: where the log comes from, what amortized actually promises, and when the constant factor decides.
A bound has a log n in it. What is almost always happening in the code to produce it?
Complexity derivation
Some quantity is repeatedly halved — a range, a count, a height — so the number of rounds is log n
A logarithm counts how many times you can halve n before you reach one, so it appears wherever each round throws away a constant fraction of what is left. Binary search discards half the range per probe, a balanced tree halves the candidates per level, merge sort halves the range per split. If nothing shrinks by a fraction, there is no log to find.
See it run — One probe at index 7 rules out indices 0–7 — half the array gone on a single comparison.
Binary search halves the live range; a 4-ary search quarters it. Why are both O(log n)?
Complexity derivation
Changing the base of a logarithm multiplies it by a constant, and Big-O discards constant factors
log₄ n is log₂ n divided by two, so the two differ by a fixed multiplier no matter how large n gets. Big-O deliberately erases multipliers, which is why no base ever appears in the notation. An interviewer will not care which base you meant, but will care if you claim the quartering is asymptotically faster.
So is a 4-ary search actually faster than binary search on an in-memory sorted array?
Comparison
No — it halves the number of rounds but spends up to three comparisons in each, so the total rises
Each round of a 4-ary search must pick one of four quarters, which takes up to three comparisons rather than one. It runs half as many rounds, so the product lands near 1.5 times binary search’s comparison count. Higher fan-out does pay on disk and in B-trees, because there the cost being minimised is block reads rather than comparisons.
“Amortized O(1)” and “average-case O(1)” are different promises. What is the difference?
Complexity derivation
Amortized bounds any sequence of operations with no probability involved; average case bounds a random input
An amortized bound is a worst-case claim about a whole sequence: n appends to a dynamic array cost O(n) in total, in any order, with no assumption about the data. An average-case bound is a claim about a distribution — quicksort’s n log n assumes a random or randomised pivot, and an adversary who knows the pivot rule can defeat it. Nobody can defeat an amortized bound by choosing inputs, which makes it the stronger of the two.
Your append is amortized O(1), yet a game loop drops a frame whenever the buffer grows. Is the bound wrong?
Trade-off & selection
No — the bound covers total cost across a sequence and says nothing about any one call’s latency
Amortization is honest about throughput and silent about tail latency, so a rare O(n) copy is a genuine stall even while the bound stays true. For a frame budget the fixes are operational: reserve the capacity up front, or use a chunked structure that grows by allocating a new block instead of copying everything. Saying “amortized O(1), but the resize is a real O(n) stall” is the answer an interviewer is listening for.
Why do dynamic arrays grow by doubling instead of by adding a fixed 1,000 slots?
Complexity derivation
Doubling makes the total copying across n appends linear; fixed growth makes it quadratic
With doubling, the copies cost 1 + 2 + 4 + … + n, a geometric series that sums to under 2n, so each append pays O(1) amortized. Adding a fixed k slots forces a copy every k appends, and those copies sum to about n²/2k — quadratic. The growth factor is what makes the amortized claim true; whether it is 2 or 1.5 is a memory-versus-copying tuning choice.
What invariant does the dynamic array’s amortized O(1) append argument actually rest on?
Invariant identification
Just after a copy into capacity c, at least c/2 slots are free, so c/2 cheap appends must precede the next copy
Doubling means the copy that just happened bought c/2 empty slots, and every one of them must be filled by an O(1) append before another copy can occur. Each expensive operation is therefore paid for by the cheap operations preceding it, which is precisely the accounting an amortized argument needs. The invariant is about the gap between expensive operations: remove it, as fixed-size growth does, and the bound collapses.
At n = 1,000,000, roughly how much work separates an O(n log n) sort from an O(n²) one?
Comparison
About 50,000 times — some 20 million operations against a trillion
n log n at a million is about 20 million steps, while n² is 10¹², a trillion. The ratio is n over log n, roughly 50,000 here — the difference between a blink and an afternoon, and no constant factor closes it. This is the rung of the ladder where most real timeouts live.
Insertion sort is O(n²) and merge sort is O(n log n). Why do production sorts call insertion sort anyway?
Trade-off & selection
Below roughly 30 elements its far smaller constant wins, and the recursion leaves exactly such ranges
Big-O ranks growth rather than wall clock, and at n = 20 a tight shifting loop beats allocating a buffer and making recursive calls. Insertion sort also runs close to linearly on nearly-ordered data, which is what a partly-sorted range looks like. Every production hybrid — introsort, Timsort — is built on exactly this crossover.
An inner loop runs n−1 times, then n−2, then n−3, down to 1. What is the total work?
Complexity derivation
About n²/2 operations, so the bound is O(n²)
The sum 1 + 2 + … + (n−1) is n(n−1)/2, so the visible shrinking shows up as a constant factor of one half and nothing more. Big-O discards the half, leaving O(n²). Triangle-shaped double loops — selection sort, bubble sort, any pairwise scan — are quadratic even though they plainly do less work than a full square.
A while loop sits inside a for loop, and the inner pointer is never reset. Is the code quadratic?
Complexity derivation
No — the inner pointer can advance at most n times across the entire run, so the total is O(n)
The bound comes from counting how many times the inner body can execute over the whole run, not from how deeply it is nested. A pointer that only ever moves forward across n elements can move n times, however those moves are distributed across outer iterations. This aggregate argument is what makes sliding-window and two-pointer scans linear despite looking like double loops.
See it run — The window slides by one addition and one subtraction — the right edge never moves backwards.
A loop over n items calls `items.shift()` each pass to take the front element. What does it really cost?
Code diagnosis
O(n²) — each shift moves every remaining element down one slot
Removing from the front of a contiguous array shifts every element after it, so one innocent line is a linear pass. Doing that n times produces the same triangle sum as any other quadratic scan. The fix is to walk with an index instead, or to use a structure whose front removal is genuinely O(1), such as a deque.
A candidate says their graph traversal is “O(n)”. Why does the interviewer push back?
Code diagnosis
“n” is ambiguous on a graph — the honest bound is O(V + E), and E can be far larger than V
Half of all complexity mistakes are really ambiguity about which quantity is growing. A dense graph has E close to V², so “linear in n” could mean linear or quadratic depending on what n was meant to be. Naming the parameters — V and E for graphs, n and m for two strings, n and W for knapsack — is what makes a bound checkable.
Asked for quicksort’s complexity, a candidate answers “O(n log n)”. What is missing?
Edge case reasoning
That this is the average case, that the worst case is O(n²), and which inputs trigger it
Unqualified, “what is the complexity?” conventionally means the worst case, so giving the average without saying the word leaves the answer incomplete. The pattern that closes it is “average X, worst Y, triggered by Z”. For the quicksort on this site, Z is repeated extreme pivots — and all-equal keys under Lomuto partitioning are the version you can watch happen.
See it run — A whole partition pass over 16 equal keys settles one element — the shape that makes it quadratic.
Bubble sort is O(n²). Under what condition does it finish in O(n), and why?
Edge case reasoning
When a full pass makes no swaps: that pass proves the array is sorted, so the rest are skipped
The swapped flag turns bubble sort into an adaptive sort: one clean pass is a proof of sortedness, so the remaining passes are unnecessary. Sorted input therefore costs a single pass of n−1 comparisons and no swaps at all. Best, average and worst are three different numbers for the same code, which is why asking “which case?” is never pedantic.
See it run — The early-exit annotation fires after one clean pass: 58 recorded steps here against 415 on reversed input.
A function sorts its input, and then runs a nested double loop over it. What is the bound?
Complexity derivation
O(n²), because the quadratic phase dominates the n log n sort
Sequential phases add, so the cost is n log n + n², and a sum is dominated by its largest term as n grows. Only nested work multiplies — a sort inside the inner loop would genuinely give n² log n. Writing the unsimplified sum first and then dropping the smaller term avoids both mistakes.
Binary search runs over 16 sorted values. How many probes does it make before it can stop?
Trace prediction
At most four, since 16 halves to 8, then 4, then 2, then 1
Each probe discards half the live range, so the probe count is the number of halvings that take 16 down to 1 — four, which is log₂ 16. That is why a million values need only about twenty probes. In the recorded run the probes land on indices 7, 11, 9 and finally 10, where the target sits.
See it run — The fourth and final probe sets mid = 10, after three earlier probes cut the range from 16 candidates to 1.
Is it correct to say “binary search is O(n²)”? And is it useful?
Comparison
Correct but useless — O is an upper bound, and a loose upper bound carries no information
O is an upper bound, so a function bounded by log n is also bounded by n², by n³, and by anything larger. Θ is the notation that claims a bound in both directions, which is what people usually mean when they say an algorithm “is” some complexity. In an interview the convention is to give the tightest bound you can and to name the case it describes.
Explain to a junior engineer what Big-O tells you and what it hides. Say it out loud before revealing.
Explain it plainly
Big-O answers one question: when the input gets bigger, how much worse does this get? It is not a speed. Double the input and a linear algorithm does twice the work, a quadratic one does four times, and a logarithmic one barely notices — that ratio is the whole content of the notation. What it deliberately throws away is the multiplier, so a quadratic algorithm with a tiny constant can beat a linearithmic one on small inputs all day, which is exactly why real sorts fall back to insertion sort under about thirty elements. Two things I would always add unprompted: which case I mean, because quicksort is n log n on average and n² when the pivots go badly, and what the memory costs, because recursion depth is space and an n-element buffer is space. So the useful sentence is never just “it is O(n log n)” — it is “average n log n, worst n², triggered by this input shape, and it needs an extra array the size of the input”.
A strong answer separates growth from speed, names which case is being described, and volunteers what the notation throws away. The test is whether the listener could use the answer to make a decision rather than to pass a quiz.