Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 5 / a / iii / Solution

The two-list functional queue has constant-time peek and isEmpty, but an individual insertion or removal can cost linear time when it reverses a rear list of length $k$. Its useful guarantee is constant amortized time per operation along a single history starting from empty.

For the amortized analysis, each item is consed into the rear once, transferred into the front at most once, and removed at most once. Charge its future reversal to the earlier insertion. Thus $m$ operations perform only $O(m)$ total list-cell work. More formally, use potential $\Phi =C|\text{rear}|$, with $C$ sufficient to pay the per-cell reversal cost. An insertion into a nonempty front increases $\Phi$ by $C$ and has constant actual cost; a reversal of $k$ cells decreases $\Phi$ by $Ck$, paying its actual cost. With ${\Phi }_0=0$ and ${\Phi }_m\ge 0$,This amortized analysis is deterministic, not an average over a random workload. It assumes subsequent operations use the successive returned versions. If a persistent old version with a long rear is reused repeatedly, each independent dequeue can redo the same reversal. The simple potential accounting does not give constant amortized cost across such a branching history without further memoization or a stronger persistent FIFO queue implementation.