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

Use the usual unit-cost model for Standard ML list constructors and fixed-size arithmetic. The input size $n$ in the list examples is the number of list elements, rather than the size of the integer entries. Inspecting only the first constructor has constant time complexity:No tail is traversed. The running time is $\Theta (1)$.