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.
814 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.let arr = new Array(1);
let n = 0;
let cap = 1;
for (let i = 0; i < 8; i++) {
if (n === cap) {
const next = new Array(cap * 2);
for (let j = 0; j < n; j++) next[j] = arr[j];
arr = next;
cap *= 2;
}
arr[n++] = i;
}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).class TinyMap {
constructor() {
this.cap = 4;
this.slots = new Array(this.cap).fill(null);
this.size = 0;
}
set(k, v) {
if ((this.size + 1) / this.cap > 0.75) this._grow();
this.slots[this.size] = [k, v];
this.size++;
}
_grow() {
const old = this.slots;
this.cap *= 2;
this.slots = new Array(this.cap).fill(null);
for (let i = 0; i < this.size; i++) this.slots[i] = old[i];
}
}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.function pushN(n) {
let arr = new Array(1);
let size = 0;
let cap = 1;
for (let i = 0; i < n; i++) {
if (size === cap) {
const next = new Array(cap * 2);
for (let j = 0; j < size; j++) next[j] = arr[j];
arr = next;
cap *= 2;
}
arr[size++] = i;
}
return arr;
}