Data Structures, Algorithms, & Applications in C++
Chapter 10, Exercise 41
The expected length of a chain is alpha.
An unsuccessful search will have to examine all nodes on the
home bucket chain. So,
Un approx = alpha
When the ith element is inserted, its
home bucket chain has an expected length (i - 1)/b.
Since the element is added at the end of the chain and since its position from
the front does not change later, 1 + (i - 1)/b
nodes are examined to locate it later.
Therefore,
Sn
approx =
1/n(sum from 0 to n-1) (1 + (i-1)/b))
approx =
1/n(sum from 0 to n-1) (1 + i/b))
=
1/n(n + n(n-1)/(2b)))
=
1 + (n-1)/(2b)
approx =
1 + alpha/2