Question Bank
Amortized Analysis Quick Quiz
Difficulty: Easy
Short drills on amortized cost for dynamic arrays, hash table rehashing, and the aggregate method. Good for solidifying the gap between worst-case and average-case-per-operation.
Amortized Analysis Quick Quiz
Short drills on amortized cost for dynamic arrays, hash table rehashing, and the aggregate method. Good for solidifying the gap between worst-case and average-case-per-operation.
813 views
14
Trace the pushes below. How many element copies happen in total across all 8 pushes when the underlying array doubles starting from capacity 1?
Examples
Example 1:
Input: finalSize = 8 (the underlying array doubles from capacity 1)
Output: 7
Explanation: Resizes happen at sizes 1, 2, 4, copying 1 + 2 + 4 = 7 elements in total.Example 2:
Input: finalSize = 16
Output: 15
Explanation: Resizes happen at sizes 1, 2, 4, 8, copying 1 + 2 + 4 + 8 = 15 elements, still bounded by 2 * finalSize.A dynamic array grows by fixed +10 slots every resize instead of doubling. What is the amortized cost of push, and why is that worse than doubling?
Insert 6 distinct keys into the hash table sketch below, which rehashes whenever load factor exceeds 0.75. How many total slot writes (including rehash copies) occur?
Examples
Example 1:
Input: insert 6 distinct keys into an empty TinyMap (initial cap = 4, grow threshold = strictly > 0.75)
Output: 9 slot writes
Explanation: Inserts 1, 2, 3 each write 1 slot at cap = 4 (running total 3). Insert 4 triggers _grow, copying 3 entries and writing the new entry (total 7). Inserts 5 and 6 each write 1 more (total 9).Use the aggregate method on this pushN(n) sketch. Compute T(n) (total writes including resize copies) and the amortized cost per push.
Examples
Example 1:
Input: measure(1024)
Output: about 2.0
Explanation: T(n) sums n direct writes plus the geometric resize copies bounded by 2n, so T(n) / n converges to roughly 2 as n grows. Amortized cost per push is O(1).Example 2:
Input: pushN(8)
Output: an array of length 8 holding 0..7
Explanation: Eight pushes trigger resizes at sizes 1, 2, 4 (copying 7 elements) and 8 direct writes, for 15 total writes, which is under 3 * 8.