1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think $n$ is being used with two different meanings: it is both the occupancy of the table and the length of the sequence. $\endgroup$ – Yuval Filmus May 9 at 12:20
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 9 at 12:21
2
$\begingroup$

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$.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 . $\endgroup$ – Vinay Varahabhotla May 9 at 14:29
  • $\begingroup$ Suppose we put 200 items in a hash table whose capacity is 100 items. Would anything go wrong? $\endgroup$ – Yuval Filmus May 9 at 14:44
  • $\begingroup$ 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 . $\endgroup$ – Vinay Varahabhotla May 9 at 15:06
  • $\begingroup$ 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 $\endgroup$ – Vinay Varahabhotla May 9 at 15:07
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 9 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.