Say what n is first
Almost every complexity argument that goes wrong goes wrong here. A bound is a function of the input size, so the size has to be named. For a dynamic array it is the number of appends. For a graph algorithm there are two sizes and "O(n)" is meaningless - you owe both V and E. For a matrix, n might be the side length or the number of cells, and O(n²) versus O(n) is the same algorithm described two ways. For an algorithm whose input is a number, the size is the number of bits used to write it down, which is the distinction the final section turns on.
Then count the dominant operation and multiply by what one costs. Stating a bound as "number of states times cost per transition" or "number of pops times cost per pop" survives the case where the per-step cost is not constant; reading a bound off the nesting depth of the loops does not.
Deriving the append bound
void add(E element) {
if (size == data.length) {
data = Arrays.copyOf(data, data.length * 2);
}
data[size++] = element;
}
Over n appends starting from capacity 1, a resize happens when the size reaches 1, 2, 4, 8, and so on up to the largest power of two below n. Each resize copies exactly as many elements as the old capacity, so the total copying work is 1 + 2 + 4 + ... + 2^k where 2^k < n. That geometric sum equals 2^(k+1) - 1, which is less than 2n.
So n appends cost fewer than 2n copies plus n constant-time writes, giving O(n) in total and O(1) per append on average across the sequence. This is the aggregate method: bound the whole sequence, then divide. There is no probability anywhere in it.
The load-bearing detail is that capacity grows by a multiplicative factor. Any constant factor above one produces a geometric series and the same O(1) amortised result - OpenJDK's ArrayList grows by roughly half again rather than doubling, and the bound is identical. Growing by a fixed increment c does not: you then resize n/c times, the i-th resize copying i·c elements, and the total is quadratic in n, making each append O(n) amortised. Being able to say why one is fine and the other is not is the actual content of the question.
Amortised is not average, and not a guarantee about one call
Here is where the defence has to be precise, because the interviewer's objection is correct on its own terms: one specific append does copy the entire array and is genuinely O(n).
Amortised O(1) is a claim about any sequence of n operations, and it holds unconditionally - there is no input distribution, no randomness, no adversary that can defeat it. Average-case is a different claim entirely: it is an expectation over a distribution of inputs, and an adversary who controls the input can push you off it. Quicksort's O(n log n) is average-case, and unlucky pivots really do produce O(n²). Hash map lookup is O(1) expected, which depends on the hash function spreading keys, so colliding keys degrade it. Dynamic array append is O(1) amortised, which depends on nothing.
What amortised does not give you is a per-operation latency bound, and that is the part worth volunteering unprompted. If you are inside a request with a p99 budget, or in a real-time or garbage-sensitive path, the amortised figure is the wrong number to plan against: occasionally one append will copy a million references and allocate a new array. The mitigations are to presize the structure when the final count is known, or to use a chunked structure that never copies. A candidate who says "amortised O(1), but the worst single call is O(n), which matters if you care about tail latency" has answered a level above one who just says the bound.
The same aggregate reasoning appears wherever a loop's inner work is bounded globally rather than locally. A monotonic-stack scan has a while inside a for, and any single iteration can pop the whole stack, yet each index is pushed once and popped at most once, so the inner body runs at most n times in total across the whole scan.
Pseudo-polynomial versus polynomial
The 0/1 knapsack table runs in O(n·W) time, with n items and capacity W. That looks like a polynomial, and it is a polynomial - in n and in the numeric value of W. It is not polynomial in the size of the input.
The input is written down in bits. Encoding the capacity takes about log₂ W bits, so if b is the number of bits spent on W, then W = 2^b and the running time is O(n·2^b): exponential in the length of the input. An algorithm whose running time is polynomial in the numeric values appearing in the input, but exponential in the input's encoded length, is called pseudo-polynomial.
That resolves the apparent contradiction in the fourth follow-up. Subset-sum is NP-complete, and a genuinely polynomial algorithm for it would settle P versus NP; the O(nW) table is not one, because W can be astronomically large while its written form stays short. Doubling the number of digits in W squares the runtime.
The distinction has a practical edge as well as a theoretical one. If the problem guarantees that W is bounded by a polynomial in n - small integer weights, a capacity in the thousands - then O(n·W) is polynomial for that input family and the table is a perfectly good algorithm. The bound has not changed; what changed is the relationship between the numbers and the input size. Trial division for primality is the same story: O(√N) sounds cheap and is hopeless for a 2048-bit modulus, because √N is exponential in the number of digits of N.
Every complexity claim carries an implicit "with respect to what", and the three that get elided are which variable, over what sequence, and under whose choice of input. Naming those explicitly is the difference between quoting a bound and defending one.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).