@Gene : Thanx for the reply. Understood your point. On Tue, Mar 6, 2012 at 6:24 AM, Gene <[email protected]> wrote:
> 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 <[email protected]> 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 <[email protected]> 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 [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. > > -- 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.
