suppose the problem is
Problem 4: Find all unique pairs of element in an array that sum to S. For
ex. If array = {2,4,6,4,6} and S = 8 then answer is {<2,6>, <4,4>}suppose we use STL c++ hash class to solve the problem . In the first we hash all the elements . in the second pass we take each element and subtract it from '8' and then we search for that difference in the hash table. if it is found then the pair exists .otherwise it does not exist. My questions are 1) What is the space complexity used by hash table . is it O(n) becoz 'n' elements are hashed into hash table. 2) Does the time to search an element is hash table is still O(1) ,but there are 'n' elements in hash table .Then how could it be O(1) Please clear my above doubts .These doubts are haunting me .I am very thankful to them ... On 27 October 2011 06:18, Prem Krishna Chettri <hprem...@gmail.com> wrote: > If N Element is already hashed and when you insert next element , Does > hashing will take log N time to find the next available position? Actually > the next insertion typically does not have any co-relation to pre-existing > table content (Until your Hash function is badly designed to hash always on > the same key everytime). So, its actually the design of Hash that has to be > efficient.Hence every operation cannot be mapped to the number of data which > is present in the existing table. > > > On Thu, Oct 27, 2011 at 12:49 AM, ligerdave <david.c...@gmail.com> wrote: > >> from high level and with a very few collisions, it's O(1). >> >> there isn't much to prove because this is based on a common sense. >> >> for example, have the world as a hashtable and all countries as the keys >> of it. boxes(storage) marked by different country names(key) and you know >> where to locate them. now, you are given a mail and asked to put it into the >> box which goes to its destination country. >> so how many operations does it take you to put a mail in the box? 1 >> if you realized the mail wasn't misplaced and you need to take it out, how >> many operations does it take you to take the mail out of the box? >> >> i hope this helps a bit >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/ZamCyJETdscJ. >> >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
