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.

Ancestors (11)

  1. d
  2. 1
  3. Paper 5
  4. ia
  5. 2006
  6. Past exam of the mathematics course of the University of Cambridge
  7. Mathematics course of the University of Cambridge
  8. Course of the University of Cambridge
  9. University of Cambridge
  10. List of universities
  11. 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