Analysis of Universal Hashing

Question

I was reading universal Hashing from Introduction to Algorithms by Cormen et al., and came across the following corollary regarding search, insert and delete functions on Universally Hashed tables:

Corollary 11.4

Using universal hashing and collision resolution by chaining in an initially empty table with $m$ slots, it takes expected time $\Theta(n)$ to handle any sequence of $n$ Insert, Search, and Delete operations containing $O(m)$ Insert operations.

Proof Since the number of insertions is $O(m)$, we have $n = O(m)$ and so $\alpha = O(1)$. The Insert and Delete operations take constant time and, by Theorem 11.3, the expected time for each Search operation is $O(1)$. By linearity of expectation, therefore, the expected time for the entire sequence of $n$ operations is $O(n)$. Since each operation takes $\Omega(1)$ time, the $\Theta(n)$ bound follows. $\quad\blacksquare$

1. How is the author able to say that $n = O(m)$, in the first line of the proof?

2. Also, what does $n=O(m)$ mean? Because $n$ is a variable and $m$ is a constant, therefore the statement seems wrong.

3. Also, if $n=O(m)$ is true, then obviously $n=\Omega(m)$ is true, thus yielding $n=\Theta(m)$.

Answer 1

The statement of the corollary is extremely sloppy. Here is a correct statement and proof.

Corollary 11.4

Fix $c < 1$. Using universal hashing and collision resolution by chaining in an initially empty table with $m$ slots, it takes expected time $\Theta(N)$ to handle any sequence of $N$ Insert, Search, and Delete operations containing at most $cm$ Insert operations.

Proof Since the number of insertions is at most $cm$, we have $n \leq cm$, where $n$ is the number of elements in the table, and so the load factor satisfies $\alpha \leq c$. The Insert and Delete operations take constant time and, by Theorem 11.3, the expected time for each Search operation is $O(1)$. By linearity of expectation, therefore, the expected time for the entire sequence of $N$ operations is $O(N)$. Since each operation takes $\Omega(1)$ time, the $\Theta(N)$ bound follows. $\quad\blacksquare$

Roughly speaking, there are two problems with the book version:

1. The variable $n$ is used both for the number of elements in the table and for the number of operations.
2. The number of Insert operations should be $O(m)$, with a hidden constant bounded away from $1$.