Exercises — Load factor — when to resize, rehashing cost

WHAT we do: plug straight into $\alpha =n/m$. $\alpha =\frac{n}{m}=\frac{12}{16}=0.75$ WHY: the load factor is defined as keys-per-bucket. Nothing more to compute. Answer: $\alpha =0.75$.

In open addressing every key lives in its own slot, so you can never store more keys than there are slots: $n\le m$, hence $\alpha =n/m\le 1$. A value $\alpha =1.3$ would mean $n>m$ — more cars than parking spaces — which cannot happen. Answer: open addressing requires $\alpha \in [0,1)$; $1.3$ violates $n\le m$.

WHY this formula: for a failed search we keep probing occupied slots until we hit an empty one; the expected count is bounded by the geometric-series result $1/(1-\alpha )$. $\mathbb{E}[P]\le \frac{1}{1-\alpha }=\frac{1}{1-0.8}=\frac{1}{0.2}=5$ Answer: at most $5$ probes.

WHAT: we want $\frac{n}{m}\le {\alpha }_{\max }$. Rearranged: $m\ge \frac{n}{{\alpha }_{\max }}$. $m\ge \frac{3000}{0.6}=5000$ WHY round up to a power of two: the slot of a key is $h(k)\mathrm{mod}m$ (defined in the symbol box above). When $m=2^t$ the operation $h(k)\mathrm{mod}m$ equals keeping the lowest $t$ bits of $h(k)$ — a single fast bit-mask instead of a slow division. The next power of two $\ge 5000$ is $2^{13}=8192$. Answer: $m\ge 5000$, choose $m=8192$.

$\alpha =\frac{40}{10}=4$ Expected chain length scanned is exactly $\alpha =4$. Total expected search cost: $O(1+\alpha )=O(1+4)=O(5)$ WHY: the "$1$" is the hash-and-index step (always happens); the "$\alpha$" is the average number of keys in the bucket you must walk past. Answer: expected chain length $=4$; expected cost $O(1+\alpha )=O(5)$.

Rehashes fire when the size must double: at sizes $1\to 2,2\to 4,4\to 8,8\to 16$. The moved count each time equals how many keys already sat in the table: $\text{moves}=1+2+4+8=15$ This is the geometric series $1+2+\cdots +2^{t-1}=2^t-1$ with $2^t=16$, giving $16-1=15$. Compare to $2n$: $2n=32$, and $15\le 32$, matching the parent's bound "total move work $\le 2n$." WHY it amortizes: those $15$ moves are shared across $16$ cheap inserts, so per insert the extra work is $15/16<1$ — a constant. See Amortized Analysis. Answer: total moves $=15$; per-insert amortized cost $O(1)$.

WHAT: with additive growth $+c$ ($c=4$), a rehash happens every $c$ inserts. The $k$-th rehash moves about $k\cdot c$ elements (the table has grown to $kc$ keys by then). Number of rehashes $\approx n/c=100/4=25$. Total moves: ${\sum }_{k=1}^{25}k\cdot c=c{\sum }_{k=1}^{25}k=4\cdot \frac{25\cdot 26}{2}=4\cdot 325=1300$ As a closed form this is $\approx \frac{n^2}{2c}=\frac{100^2}{2\cdot 4}=1250$ — same order, $\Theta (n^2)$. Amortized per insert: $1300/100=13$ moves, and this ratio grows with $n$ → amortized $\Theta (n)$, not constant. WHY this is bad: unlike doubling, the series is arithmetic ($1+2+\dots$), which sums to $\Theta (n^2)$ instead of a geometric $\Theta (n)$. Answer: $\approx 1300$ moves, amortized $\Theta (n)\approx 13$ moves/insert (and worsening).

The danger (thrashing): if you grow at $\alpha >0.5$ and shrink at $\alpha <0.5$, one insert can push $\alpha$ just above $0.5$ (grow, cost $\Theta (n)$), then one delete pulls it just below $0.5$ (shrink, cost $\Theta (n)$), forever — $\Theta (n)$ per op. The fix — hysteresis (a gap between thresholds):

• Grow ($m\to 2m$) when $\alpha >0.75$.
• Shrink ($m\to m/2$) when $\alpha <0.25$.

Why the gap saves us — check the post-resize load factor:

• After a grow ($m$ doubles, $n$ unchanged): $\alpha$ halves from just above $0.75$ to just above $0.375$. That is comfortably above the shrink line $0.25$, so no delete can immediately trigger a shrink.
• After a shrink ($m$ halves): $\alpha$ doubles from just below $0.25$ to just below $0.5$. That is comfortably below the grow line $0.75$, so no insert can immediately trigger a grow.

Because each resize leaves you far from the next threshold, you must perform $\Theta (m)$ ops to cross a boundary again — so the $\Theta (n)$ resize cost amortizes over $\Theta (n)$ ops → $O(1)$ each. Answer: grow at $0.75$, shrink at $0.25$; after any resize $\alpha$ lands in $[0.375,0.5]$, a safe zone away from both thresholds.

Setup — two kinds of work.

1. The placement of each key itself — writing one key into its slot — costs $1$. Over $n$ inserts: total $=n$.
2. Rehash moves — each time the size doubles we re-insert all keys currently present.

Rehash work (careful with bounds). Starting at size $1$ and inserting $n=2^t$ keys, doublings are triggered as the table fills at sizes $1,2,4,\dots ,2^{t-1}$. The rehash that grows the table from size $2^j$ moves the $2^j$ keys sitting in it. So the moves are $\text{rehash moves}={\sum }_{j=0}^{t-1}{2}^j=2^t-1=n-1$ using $1+2+\cdots +2^{t-1}=2^t-1$. Note: the top index is $t-1$, not $t$ — the final size $2^t=n$ never itself overflows within these $n$ inserts, so it triggers no move. This is the summation bound that must be $t-1$.

Grand total. $\underset{\text{placements}}{\underbrace{n}}+\underset{\text{rehash moves}}{\underbrace{(n-1)}}=2n-1=\Theta (n)$ Amortized per insert: $\frac{2n-1}{n}=2-\frac{1}{n}=O(1)$

Check for $n=8=2^3$ (so $t=3$):

• rehash moves $={\sum }_{j=0}^2{2}^j=1+2+4=7=n-1$ ✓ (the doublings $1\to 2,2\to 4,4\to 8$).
• placements $=8$.
• total $=8+7=15=2n-1$ ✓.

Everything is now consistent: rehash moves $=n-1=7$, total cost $=2n-1=15$. Answer: total $=2n-1$; for $n=8$ that is $15$; amortized $O(1)$.

Step 1 — bound $\alpha$ from the probe target. We need $\frac{1}{1-\alpha }\le 4\Rightarrow 1-\alpha \ge \frac{1}{4}\Rightarrow \alpha \le 0.75$ WHY invert like this: $1/(1-\alpha )$ is increasing in $\alpha$; capping the output at $4$ caps the input $\alpha$ at $0.75$. Step 2 — size the table. $m\ge n/{\alpha }_{\max }=6000/0.75=8000$. WHY round to a power of two: exactly as in Exercise 2.2 — with $m=2^t$, the slot computation $h(k)\mathrm{mod}m$ becomes a bit-mask (keep the low $t$ bits of $h(k)$) instead of a slower division. The next power of two $\ge 8000$ is $2^{13}=8192$. Answer: ${\alpha }_{\max }=0.75$; minimum $m=8000$, choose $m=8192$.

Definition ($\alpha =n/m$) → pick the right cost formula ($1+\alpha$ vs $1/(1-\alpha )$) → doubling gives geometric move-work $\to \Theta (n)$ total $\to O(1)$ amortized → hysteresis stops thrashing → but worst-case single insert is still $\Theta (n)$.