intro practice · coding problem
Amortised growth of a dynamic array
Implement pushCount(n): build a dynamic array by pushing n items, doubling capacity when full (starting at capacity 1), and return the TOTAL number of element copies performed. This is the sum that makes push O(1) amortised — for n=8 the copies are 1+2+4 = 7.
The mechanism
A complexity bound is a claim about growth, not speed: it says how the work scales as n grows, so constants and hardware drop out. Amortised cost is a separate claim — that an expensive step is rare enough to average down over a sequence, which is why a dynamic array's push is O(1) amortised despite occasionally copying everything. Space is the third axis and the one people forget: recursion depth is memory.
Expected evidence
pushCount(8) -> 7, pushCount(1) -> 0, pushCount(100) -> 127
Try this drill in the practice workspace →
Hints when you need them
- You only copy at the moment capacity is exhausted, and you copy everything currently stored.
- Capacities go 1, 2, 4, 8 … so the copies form a geometric series that sums to less than n.
Watch for these mistakes
- Reporting the complexity of the loop you can see and missing the one inside the library call (sort, includes, string concat)
- Calling an amortised bound a worst-case bound — a single push can still be O(n)
- Ignoring recursion depth, so an O(n) algorithm quietly uses O(n) stack
- Adding complexities of sequential phases instead of taking the max, or multiplying nested loops that do not actually nest over the same n