What Don so succinctly said is this: Comparison sort _requires_ O(n log n) comparisons. If you had the data structure you're asking for, you could easily implement a comparison sort: Just insert n items, then then repeat n times: find min and delete that min. With your proposed time bounds, the resulting sort would be O(n). This is how you can immediately tell what you're asking for is impossible.
On Mar 5, 5:51 pm, Sehaj Singh Kalra <sehaj...@gmail.com> wrote: > Ok. Got it. I think that without the assumption that you took ( about FIFO > implementation i.e. only the recent most element to be added can be deleted > or else there would be problem in updating stack 2) the problem can't be > done. Thanks for the proposed solution. > > On Tue, Mar 6, 2012 at 4:13 AM, SAMM <somnath.nit...@gmail.com> wrote: > > As I mentioned we have to use hashing using Separate Chaning to find the > > element in constant time . This is different than than opening addresing > > which added the element to the next free slot in case of a collision , so > > we cann't keep track of the element in a constant . In sepate Chaning the > > elements when collision is found the element will be in the stored in the > > form of the linked list on the same slot . IN worst case if all the element > > give collision then the time complexity can be of O(n) . But chossing the > > proper hash key can give the result in constant time . > > > -- > > 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. -- 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.
