Given a string s and a hashset of strings words, what is the time complexity of the operation: s in words? Assume all strings have length M. My current guess is O(M) to compute the hash of s, O(1) to find that bucket in the hash table, and O(M*number of strings in the bucket) to compare the strings in the bucket and the s , so a total of O(M*number of strings in the bucket). Not assuming any fancy string comparison algorithms here--want to focus more on the other parts.

  • 1
    $\begingroup$ Analysis of hash tables depends a lot on the assumptions you want to make. Do you want an analysis that will be useful in practice, or do you care more about theoretical worst-case behavior? Can we make reasonable assumptions about the load factor of the hash table? Can we use expected running time? etc. $\endgroup$ – D.W. Nov 6 '20 at 7:14
  • $\begingroup$ @D.W. Maybe we can consider various reasonable scenarios? Say both avg and worst case behavior? Yes i think we can make reasonable assumptions about the load factor--let's not assume it is very skewed. Let's also use expected running time, and maybe talk a little bit about scenarios in which the worst case occurs. $\endgroup$ – ved Nov 6 '20 at 22:14

Your Answer

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

Browse other questions tagged or ask your own question.