Amortised Analysis and BFS with Queues

Amortised O(1) analysis

Consider an execution starting from an empty queue with n enq operations and n deq operations, in any order.

• Each enq performs one ::: adds element to rear list. Total: n conses.
• Each element is transferred from rear to front exactly once during a norm reversal. Each transfer costs one ::. Total: n conses.
• Total cost: 2_n_ cons operations for 2_n_ operations.
• Average: 2 cons per operation = O(1) amortised.

This is amortised analysis: the cost per operation averaged over the lifetime of a complete execution. Even for the worst possible execution sequence, the average is constant.

The catch

The conses are not distributed evenly. A single deq that triggers a reversal could take O(n) time. This makes the two-list queue unsuitable for real-time systems where predictable deadlines matter. But for most purposes, the O(1) amortised bound is excellent.

BFS using queues

let rec breadth q =
  if qnull q then []
  else
    match qhd q with
    | Lf -> breadth (deq q)
    | Br (v, t, u) -> v :: breadth (enq (enq (deq q) t) u)
(* val breadth : 'a tree queue -> 'a list = <fun> *)

This implements the same algorithm as nbreadth but uses the two-list queue. Each iteration:

1. Dequeues the first tree.
2. If it is a leaf, continues with the rest.
3. If it is a branch with label v and children t, u: outputs v, then enqueues both children.

Performance comparison

On a full binary tree of depth 12 (4095 labels):

Implementation	Data structure	Time	Ratio
nbreadth	List + append	30.0 s	-
breadth	Two-list queue	0.15 s	200× faster

For larger trees, the speedup grows. Choosing the right data structure pays handsomely.