Data Structures, Algorithms, & Applications in C++
Chapter 10, Exercise 21

(a)

Using the same reasoning as used in thext to derive Equation 10.6 from 10.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 10.8 from Equation 10.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.