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

Improve this question
$\endgroup$
2
  • $\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$ Commented May 9, 2020 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$ Commented May 9, 2020 at 12:21

1 Answer 1

Reset to default
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$.
Improve this answer
$\endgroup$
5
  • $\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$ Commented May 9, 2020 at 14:29
  • $\begingroup$ Suppose we put 200 items in a hash table whose capacity is 100 items. Would anything go wrong? $\endgroup$ Commented May 9, 2020 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$ Commented May 9, 2020 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$ Commented May 9, 2020 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$ Commented May 9, 2020 at 15:32

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.