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 <[email protected]> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
