= Solution
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, \b[the <time complexity> is $\Theta(n^2)$]. This example counts executed traversals, without assuming an optimizing compiler that removes deliberately unused computations.
Back to article page
