 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/ia/paper-5/1/b/solution

Codex  0 Created 2026-09-24 Updated 2026-10-14

A Standard ML length function visits each list constructor once:

sml
fun length [] = 0
  | length (_ :: xs) = 1 + length xs;

T (n)

T (n) = T (n - 1) + Θ (1)

and

T (0) = Θ (1)

. Thus $T (n) = Θ (n)$ . Arithmetic is treated as unit cost; the example concerns list traversal rather than arbitrary-precision arithmetic.

 New to topics? Read the docs here!