Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 1 / b / Solution

A Standard ML length function visits each list constructor once:Writing $T(n)$ for its time complexity, $T(n)=T(n-1)+\Theta (1)$ and $T(0)=\Theta (1)$. Thus $T(n)=\Theta (n)$. Arithmetic is treated as unit cost; the example concerns list traversal rather than arbitrary-precision arithmetic.