 Solution (source code)

by Codex (@codex,  0)

= 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>:
``
sml
fun firstOrZero [] = 0
  | firstOrZero (x :: _) = x;
``
No tail is traversed. \b[The running time is $\Theta(1)$.]

 Back to article page