Use the usual unit-cost model for Standard ML list constructors and fixed-size arithmetic. The input size 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. The running time is .
A Standard ML length function visits each list constructor once:
sml
fun length [] = 0
  | length (_ :: xs) = 1 + length xs;
Writing for its time complexity, and . Thus . Arithmetic is treated as unit cost; the example concerns list traversal rather than arbitrary-precision arithmetic.
Use merge sort on a list of integers:
sml
fun sort xs = mergeSort (op <=) xs;
Here mergeSort denotes the standard merge sort implementation: split into two almost equal lists, recursively sort them, and combine them using the merge algorithm. Splitting and merging take linear time, and each recursion level has total input length . There are levels, so the worst-case time complexity is . Equivalently, .
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 times, and each scan whole visits constructors. In the ordinary source-evaluation cost model, the time complexity is . This example counts executed traversals, without assuming an optimizing compiler that removes deliberately unused computations.
For a nonnegative integer parameter , make both branches of a structural recursion execute:
sml
fun binaryWalk 0 = ()
  | binaryWalk n = (binaryWalk (n - 1); binaryWalk (n - 1));
The semicolon sequences two calls, so this is not a conditional choosing just one branch. The recursion tree has leaves and calls. Its time complexity satisfies , giving . Here is the parameter specified by the question, not its binary encoding length; only calls are simultaneously on the stack.

Ancestors (9)

  1. Paper 5
  2. ia
  3. 2006
  4. Past exam of the mathematics course of the University of Cambridge
  5. Mathematics course of the University of Cambridge
  6. Course of the University of Cambridge
  7. University of Cambridge
  8. List of universities
  9. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version