Worst Case

Let's say we insert n distinct keys into an initially empty hash table of size m and then we want to do a find. What's the running time for the find?

Load factor is $\alpha = n/m$.

Worst case for chaining?

Worst case for open addressing?


next up previous
Next: Uniform-Hashing Assumption Up: ANALYSIS Previous: ANALYSIS