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

(a)

(b)

The loading factor is 10/27 = 0.37.

(c)

The number of buckets examined during an unsuccessful search that starts at home bucket i is [1, 1, 1, 1, 1, 1, 1, 4, 3, 2, 1, 3, 2, 1, 4, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1]. The average is 42/27 = 1.56.

(d)

When searching for each of [7, 42, 25, 70, 14, 38, 8, 21, 34, 11] the number of buckets examined is [1, 1, 1, 1, 1, 1, 1, 1, 3, 2]. The average is 13/10 = 1.3.

(e)

When the loading density is 0.37, the formulas yield 1.76 and 1.29 as the expected value for the average number of buckets examined in an unsuccessful and a successful search, respectively. These numbers are quite close to those in our example. However, you should remember that the formulas do not tell you what will happen in an individual case but what happens on average as the number of elements in the table becomes very large.