 Solution

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

 Top articles  Latest articles New article in topic

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

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

Traverse the whole original list once for each of its elements:

sml
fun scan [] = ()
  | scan (_ :: xs) = scan xs;

fun scanForEach [] whole = ()
  | scanForEach (_ :: rest) whole =
      (scan whole; scanForEach rest whole);

fun quadratic xs = scanForEach xs xs;

The outer structural recursion runs

n

times, and each scan whole visits

n

constructors. In the ordinary source-evaluation cost model, the time complexity is $Θ (n^{2})$ . This example counts executed traversals, without assuming an optimizing compiler that removes deliberately unused computations.

 Read the full article

 New to topics? Read the docs here!