We can’t predict this without knowing the Hash Function h(), so worst case time complexity should be O(n). Please explain the answer.
Hashing - Q4. Number Of Collision
Hello Monica Please let me know what The Question is Asking. Provide me the question statement so that i can help you better.
Thank You Monika for sharing question
As per the defination of universal hashing it is stated that If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n ≤ m, the expected number of collisions involving a particular key x is less than 1. So That’s Why answer to this is 1 instead of n.
I hope your doubt is clear now!!
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.