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.
