An operation is constant time, or O(1), when its time is bounded independently of input size. This describes an individual operation, not necessarily an entire algorithm or sequence of operations. section 2.4
Immutable queues show why worst-case and amortized costs matter. Enqueue, Peek, and IsEmpty take constant time, but Dequeue can take O(n) when it reverses the enqueue stack. Across a sequence of operations, however, each item is moved only a bounded number of times, making dequeue amortized O(1). section 2.4
Constant-time construction, linear-time result
A Hughes list can represent reversing a stack by constructing a delegate in O(1) time. Converting that representation back to a stack takes O(n), so constant-time construction does not make the full reversal constant time. section 2.7.7
The same distinction appears in permutation generation: Fisher–Yates uses O(1) swaps, avoiding O(n) RemoveAt operations. The swap is constant time; the full algorithm performs multiple swaps. section 6.2.3
public static HList<T> Reverse(IImStack<T> fromStack) =>
fromStack.IsEmpty ?
Empty :
Make(stack => fromStack.ReverseOnto(stack));
The Reverse factory represents reversal with a Hughes list; materializing the stack remains linear time. section 2.7.7
