17.4

Exercise 17.4-3

---

Suppose that instead of contracting a table by halving its size when its load factor drops below 1/4, we contract it by multiplying its size by 2/3 when its load factor drops below 1/3. Using the potential function

$$ Φ(T) = |2 · num[T] - size[T]| $$ ,

show that the amortized cost of a TABLE-DELETE that uses this strategy is bounded above by a constant.

Answer

If the i-th deletion does not lead to a contraction, we have

\hat{c_i} = c_i + Φ_i - Φ_{i-1}

= 1 + (size_i - 2 num_i) - (size_{i-1} - 2 num_{i-1})

= 1 + (size_i + 2 num_i ) - (sum_i - 2( num_i + 1))

= 3

else if the i-th deletion lead to a contraction, we have equation

num_{i-1} = num_i + 1 = 1/3 size_{i-1} = 1/2 size_i

so

\hat{c_i} = c_i + Φ_i - Φ_{i-1}

=(1 + num_i) + (size_i - 2 num_i) - (size_{i-1} - 2 num_{i-1})

= 2

Q.E.D.