@juver, thanks for the explanation... but a few more queries... In my implementation, when I delete first element, why should we access all other elements? I should do that if the element i'm deleting is the current minimum... or is my understanding of get_min() totally wrong? I assumed get_min() should return the smallest item in the queue...
On Jan 10, 11:20 pm, juver++ <avpostni...@gmail.com> wrote: > About 2 stack implementation. > Yes some operations can be O(n) as a separate estimation. But all other will > be constant, cause we access elements at most twice. > So for the sequence of M operations (pop,push,min) total complexity will be > O(M), so the average cost of each operations is O(1). > There are no two consecutive operations which are linear. > > But in your implementation, when you delete first element, you will access > all remaining elements. So, it is O(n) for every operation of delete! > Insert M numbers, then remove all elements with accessing to the min item - > this will cost you O(M*M) for all, and O(M) in average! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
