# Question

Suppose that we have a hash table with n slots, with collisions resolved by chaining, and suppose that n keys are inserted into the table. Each key is equally likely to be hashed to each slot. Let M be the maximum number of keys in any slot after all the keys have been inserted. Your mission is to prove an O (lg n/lg lg n) upper bound on E[M], the expected value of M.

a. Argue that the probability Qk that exactly k keys hash to a particular slot is given by Qk = (1/n)k(1 – 1/n) n–k (n/k)..

b. Let Pk be the probability that M = k, that is, the probability that the slot containing the most keys contains k keys. Show that Pk ≤ n Q k..

c. Use Stirling's approximation, equation (3.17), to show that Qk < ek / kk..

d. Show that there exists a constant c > 1 such that for k0 = clg n/ lg lg n. Conclude that Pk < 1/n2< for k ≥ k0 = c lg n/ lg lg n..

e. Argue that

Conclude that E[M] = O(lg n/ lg lg n)..

a. Argue that the probability Qk that exactly k keys hash to a particular slot is given by Qk = (1/n)k(1 – 1/n) n–k (n/k)..

b. Let Pk be the probability that M = k, that is, the probability that the slot containing the most keys contains k keys. Show that Pk ≤ n Q k..

c. Use Stirling's approximation, equation (3.17), to show that Qk < ek / kk..

d. Show that there exists a constant c > 1 such that for k0 = clg n/ lg lg n. Conclude that Pk < 1/n2< for k ≥ k0 = c lg n/ lg lg n..

e. Argue that

Conclude that E[M] = O(lg n/ lg lg n)..

## Answer to relevant Questions

Suppose that we are given a key k to search for in a hash table with positions 0, 1, ..., m - 1, and suppose that we have a hash function h mapping the key space into the set {0, 1, ..., m -1. The search scheme is as ...Although merge sort runs in Θ (n lg n) worst-case time and insertion sort runs in Θ(n2) worst-case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort ...In order to transform one source string of text x [1 ¬ m] to a target string y [1 ¬ n], we can perform various transformation operations. Our goal is, given x and y, to produce a series of transformations that change x to ...Professor Midas drives an automobile from Newark to Reno along Interstate 80. His car's gas tank, when full, holds enough gas to travel n miles, and his map gives the distances between gas stations on his route. The ...Let G = (V, E) be an undirected, connected graph with weight function w : E → R, and suppose that |E| ≥ |V| and all edge weights are distinct. A second-best minimum spanning tree is defined as follows. Let be the ...Post your question

0