Average case costs with separate chaining

Assume a table with load factor
α
= N/M

There are N items total distributed over M linked lists (some of which may be empty), so the average number of items per linked list is:

In unsuccessful find/insert, one of the linked lists in the table must be exhaustively searched, and the average length of a linked list in the table is
α
. So the average number of comparisons for insert or unsuccessful find with separate chaining is

In successful find, the linked list containing the target key will be searched. There are on average (N1)/M keys in that list besides the target key; on average half of them will be searched before finding the target. So the average number of comparisons for successful find with separate chaining is

These are less than 1 and 1.5 respectively, when
α
< 1

And these remain O(1), independent of N, even when
α
exceeds 1.
CONTENTS PREVIOUS NEXT