1. Average and amortized have very different meanings in algorithmic analysis.
2. One mistake - Okasaki's queues in "Simple and Efficient Purely Functional Queues and Deques" are actually constant-time in the worst-case.
3. Okasaki makes a strong case in his book that the kind of analysis that rejects amortization over ephemeral usage when a structure can be used in a persistent setting is not "more egregious than describing quicksort as O(n^2)". Note, for instance, that quicksort is O(n log n) with high probability with good randomness, and O(n log n) in the worst case with median-of-medians. This quadratic queue case may be degenerate, but the degenerate algorithmic complexity attack of turning hash tables into linked lists by manufacturing collisions is well-documented and worth worrying about. I claim the same is true of queues if a persistent interface is exposed to the user.
1. Average and amortized have very different meanings in algorithmic analysis.
2. One mistake - Okasaki's queues in "Simple and Efficient Purely Functional Queues and Deques" are actually constant-time in the worst-case.
3. Okasaki makes a strong case in his book that the kind of analysis that rejects amortization over ephemeral usage when a structure can be used in a persistent setting is not "more egregious than describing quicksort as O(n^2)". Note, for instance, that quicksort is O(n log n) with high probability with good randomness, and O(n log n) in the worst case with median-of-medians. This quadratic queue case may be degenerate, but the degenerate algorithmic complexity attack of turning hash tables into linked lists by manufacturing collisions is well-documented and worth worrying about. I claim the same is true of queues if a persistent interface is exposed to the user.