Hi I am reading the chapter about universal hashing on CLRS.
On page 234
Corollary 11.4
Using universal hashing and collision resolution by chaining in a 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.
I kinda get the idea but I have a hard time to understand this English sentence. What does the end "containing O (m) INSERT operations" mean?
Does it mean n = O(m) insertion was performed already. Then, .... I don't know. I can't parse this sentence. What is the difference between the 1st INSERT and 2nd INSERT?
I would like to hear your opinion.
Thanks!
I think that there is only one sequence of n insert, search, and delete operations, but the parameter m is used to limit the number of insert operations you are allowed to put within those n operations. Suppose that you had a table of size 10, so m=10, and then you set n=1 000 000, with the first 500 000 operations inserts, and the next 500 000 searches for an item not in the table. Then the performance would be very poor, because the table would have chains about 100 000 items long.
So if you have a table with m slots, the theorem only allows you about m insert operations, so that the table never holds more than about m items, and the chains won't get too long, and all the operations are pretty much O(1) - in the example above you can only have about 10 insert operations, so the other 999 990 operations must be either search or delete.