[Haskell-cafe] Where is "minimumsBy"?

[Frank Staals]

Christian Sternagel <c.sternagel at gmail.com> writes:

> That is interesting. Is anybody aware of a more detailed justification
> of how lazy evaluation makes this happen? - chris

There might be a more formal argument written down somewhere, but the
gist of it should be:

Think of the recursion tree of merge sort; leaves correspond to
singleton lists, internal nodes correspond to merges of two sorted
lists. To determine the minimum element of the merged result you need to
consider only the first elements of both these lists. Hence, every node
can be charged at most O(1) times. Since the tree has size O(n) the
running time is linear.

--

- Frank