We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Amortized analysis means looking at the worst case run time distributed over the total run time. Yes, the worst case of enqueuing every element and then dequeuing one element has an O(N) run time for that one dequeue, however, in that case, every other dequeue would be O(1), so it would be N operations for N elements, which averages out to O(1). You can kinda think of it more as every enqueue you do has a 1 operation cost for pushing onto the rear stack, and a promised cost of an operation to eventually get swapped onto the front stack. If you consider that eventual swap as part of the cost of each enqueue rather than the cost of dequeuing, dequeuing is O(1) and enqueuing is O(1 + 1) = O(1).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Queue using Two Stacks
You are viewing a single comment's thread. Return to all comments →
Amortized analysis means looking at the worst case run time distributed over the total run time. Yes, the worst case of enqueuing every element and then dequeuing one element has an O(N) run time for that one dequeue, however, in that case, every other dequeue would be O(1), so it would be N operations for N elements, which averages out to O(1). You can kinda think of it more as every enqueue you do has a 1 operation cost for pushing onto the rear stack, and a promised cost of an operation to eventually get swapped onto the front stack. If you consider that eventual swap as part of the cost of each enqueue rather than the cost of dequeuing, dequeuing is O(1) and enqueuing is O(1 + 1) = O(1).