Data Structures, Algorithms, & Applications in Java
Chapter 11, Exercise 21

(a)

Using the same reasoning as used in thext to derive Equation 11.6 from 11.5, we get
Sn
approx = 1/n(sum from 0 to n-1) (1/2[1 + 1/(1-(i-1)/b)2])
approx = 1/n(sum from 0 to n-1) (1/2[1 + 1/(1-i/b)2])
approx = 1/n(integral from 0 to n-1) (1/2[1 + 1/(1-i/b)2]) di
= 1/n(from 0 to n-1) (1/2[i + b/(1-i/b)])
approx = 1/n(from 0 to n) (1/2[i + b/(1-i/b)])
= 1/(2n)(n + b/(1-n/b) - b)
= 1/2(1 + (1/alpha)(1/(1-alpha) - 1)))
= 1/2(1 + 1/(1-alpha))

(b)

This approach cannot be used directly to derive Equation 11.8 from Equation 11.7 because the distance of an inserted element from the head of its chain changes as more insertions are done. Consequently, the text makes the assumption that identifiers are inserted in ascending order of key. With this assumption, the distance of elements from the head does not change as more insertions are made. Also, the final distance from the chain head is the same regardless of the insert order because the chains are sorted.