[Haskell-cafe] Re: Producing MinimumValue

[Aaron Denney]

On 2007-07-19, Sebastian Sylvan <sebastian.sylvan at gmail.com> wrote:
> On 19/07/07, Steve Schafer <steve at fenestra.com> wrote:
>> On Thu, 19 Jul 2007 10:55:19 -0700 (PDT), you wrote:
>>
>> >The question suggests to use some functions defined in the section, and one
>> >of them is iSort.
>>
>> Aha. Well, that one certainly lends itself better to this particular
>> proplen than either map or filter.
>>
>> >minimumValue :: [Int] -> Int
>> >minimumValue ns = head (iSort ns)
>>
>> If I were going to use a sort, then yes, that's the way I would do it.
>> Of course, sorting isn't the best way to solve the problem, as sorting
>> will always be at least O(n * log n), whereas a more straightforward
>> algorithm would be O(n).
>
> Actually, since Haskell is lazy and only the first element is required
> for minimumValue, the above algorithm should be O(n).

I'm pretty sure that it's possible for to get O(n) behaviour, but that
it's not guaranteed.  It really should depends on the sort supplied.

-- 
Aaron Denney
-><-