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

(a)

(b)

The loading factor is 10/13 = 0.77.

(c)

The number of buckets examined during an unsuccessful search that starts at home bucket i is [3, 2, 1, 2, 1, 2, 1, 9, 8, 7, 6, 5, 4]. The average is 51/13 = 3.9.

(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, 2, 1, 2, 3, 1]. The average is 14/10 = 1.4.

(e)

When the loading density is 0.77, the formulas yield 9.95 and 2.67 as the expected value for the average number of buckets examined in an unsuccessful and a successful search, respectively. These numbers are higher than in our example. The discrepancy is because 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.