@ Juver, I got the following response in the group digest mail. It'll be great if you can provide some inputs so I can refine my understanding...
Could you please help me understand how my delete operation takes O(n) time for every delete? I propose to maintain the minimum at the queue level (one variable for the entire queue object) which can change on each insert (O(1) operation to see if the newly inserted item is the new minimum) and on delete of a current min item, a O(n) list traversal is required to figure out what the min is now... if the deleted item is not the current min, no updates to current minimum value need to be made... I did a little bit of reading on amortized complexity. You're definitely correct. I don't know as much as you probably do on that subject. But is the following statement about the 2 stack implementation correct? After inserting a bunch of items, say 10000, in your queue (which fills up stack 1), lets say you do delete_rear (u need to pop all items from stack 1 and push them in stack 2) and then a delete_front (pop from second stack and push all into first) in succession until the queue is empty, wont each operation cost O(n)? Based on my preliminary understanding, to estimate amortized complexity, we can ignore O(n) operations provided they occur only once in every K operations... but when there's a chance that they can occur for every 1 operation, that's the worst case scenario there. would it still be amortized... Pls Note: this is just to better my understanding.. am not challenging anybody... --------------------------------------------------------------------------------------- juver++ <avpostni...@gmail.com> Jan 10 06:25AM -0800 ^ You should analyze your algo more precisely and study something about amortized time complexity. Your delete operation takes O(n) time for EVERY query. So for the sequence of M deletetions there is an average time O(N) which is NOT constant on the worst case. -- 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.
