# Analysis of Universal Hashing

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)$$.

• I think $n$ is being used with two different meanings: it is both the occupancy of the table and the length of the sequence. – Yuval Filmus May 9 at 12:20
• The statement "$n = O(m)$" means "there exists a constant $C$ such that $n \leq Cm$". The constant $C$ depends on the hidden constant of $O(m)$ in the statement of the corollary. – Yuval Filmus May 9 at 12:21

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$$.
• Thx for the explanation, I understood the proof . But why are we restricting $C < 1$ , because that says that the number of elements in the table can never be greater than the number of slots. Even if we have $C\geq 1$ the proof seems to be working as we still have $\alpha \leq C$ for some constant $c$ therefore $\alpha =O\left( 1\right)$ , and the rest follows . P.S Thx for referring the textbook for me and correcting the question . – Vinay Varahabhotla May 9 at 14:29
• Suppose we put 200 items in a hash table whose capacity is 100 items. Would anything go wrong? – Yuval Filmus May 9 at 14:44
• Understood the hash table overflows , usually even our hash function gives wrong keys . But even if it gives keys within $h(k)$ such that $h\left( k\right) \in \left[ \begin{matrix} 0& \ldots .& m-1\end{matrix} \right]$ load factor increases . – Vinay Varahabhotla May 9 at 15:06
• Because we use chaining for dealing with collisions I thought that hash table overflows are also allowed. I read the net hash tables overflows are usually not allowed – Vinay Varahabhotla May 9 at 15:07
• You might be right. It depends on how the hash table is implemented exactly. Since only you have a copy of the book, I’ll let you figure that out. – Yuval Filmus May 9 at 15:32