NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/comp/programm/3611

Internet Message Format | 1993-01-27 | 3.3 KB

Path: sparky!uunet!comp.vuw.ac.nz!waikato.ac.nz!aukuni.ac.nz!cs18.cs.aukuni.ac.nz!jeremy
Newsgroups: comp.programming
Subject: Re: is it possible to find max & next smallest in one pass?
Message-ID: <[e-mail]>
From: [e-mail] (Jeremy Gibbons)
Date: Thu, 28 Jan 1993 01:06:59 GMT
References: <[e-mail]>
Organization: Computer Science Dept. University of Auckland
Cc: [e-mail]
Lines: 61

In <[e-mail]> [e-mail] (Michael Murphy) writes:

>>[e-mail] (Jos Horsmeier) writes:

>>>In article <[e-mail]> [e-mail] (Sean Ahern) writes:
>>>|[e-mail] (John Grant) writes:
>>>|>Given an array of values, is it possible to find the maximum of
>>>|>the array and the next smallest value in a single pass?
>>>|
>>|If you were able to do this, the algorithm should be able to extend to the
>>|next smallest, and the next, with little or no trouble.
>>|
>>|But the requirement of the algorithm was to do this in one pass.  This would
>>|give us an O(n) sorting algorithm that works on arbitrary data.  I don't
>>|believe such an animal exists with only one processor.
>>
>>I beg to differ here. Lets do some big Oh calculations. Given n elements
>>in an array, one can find the maximum value in O(n) operations. One can
>>find the next value in O(n) operations too, so both can be done in
>>O(n)+O(n)= O(2*n) operations. But constants don't count here, so the
>>whole job can be done uisng O(n) operations.
>
>This is true

No, it isn't. Or at least, not in the way you think. Generalising the
obvious algorithm for finding the largest two elements out of n to an
algorithm for finding the largest k elements out of n leads to O(nk)
comparisons (keeping a sorted list of the k largest so far), or to O(n log
k) (keeping a balanced binary tree of the k largest so far), in the worst
case. This is only O(n) if k is considered fixed, not part of the problem.

Put another way: if you allow yourself arithmetic with big Os, then
   O(n)+O(n) = O(n)
   O(n)+O(n)+O(n) = O(n)
etc, but
   O(n)+O(n)+...+O(n) [k times]  is not  O(n)
Which just goes to show that you can't trust arithmetic with big Os. :-)

>>I suppose a good way to find the k smallest elements of an array would be
>>to do a O(n*logn) sort and then pull off the smallest k elements.  Though I
>>must admit that if you only want the first 2 smallest, the O(2*n) algorithm
>>would be better for n>4.
>
>The problem of finding the k-smallest elements of an array is often called
>"Selection."  Algorithms exist that can perform Selection in guaranteed
>linear time.

Actually, "Selection" refers to finding the (single) kth-smallest element,
not to all k smallest elements. I don't know of any way of finding all k
smallest elements for arbitrary k in O(n) comparisons in the worst case.
(Information-theoretic arguments show that you can't find all k smallest
elements for arbitrary k in O(n) comparisons in the worst case *and* return
them in sorted order, because then you could sort in O(n) comparisons.)

Jeremy

---
Jeremy Gibbons <[e-mail]>         tel: [phone]
   Department of Computer Science,              fax: [phone]
   University of Auckland, Private Bag 92019, Auckland, New Zealand.