Universal hashing - insert / search / delete
Let me try to explain this with an example. Let us say if m=10 and n=1000.
If I have m number of insertions in a table with m slots, it is going to be O(m). Right?
But if we have 1000 insertions in a table containing 10 slots, it is not the same math anymore. Since you will have to deal with collisions at a greater frequency. It no more remains linear math. Thus if the n stays small enough that it is in order of O(m), you can have expected Theta n for n inserts. If inserts increase at a number much greater than m, the collisions doesn't let it be linear.