apfelmus apfelmus at quantentunnel.de
Sat Apr 14 06:33:32 EDT 2007

```ajb at spamcop.net wrote:
> You have n elements, and you need to locate a specific k-element
> permutation.  There are n! / (n-k)! such permutations.  You therefore
> need log(n! / (n-k)!) bits of information.
>
> A binary comparison provides one bit of information.  So the number of
> comparisons that you need to get that much information is:
>
>   O(log(n! / (n-k)!))
> = O(n log n - (n-k) log (n-k))
> = O(n log (n/(n-k)) + k log (n-k))
>
> That looks right to me.  If k << n, then this simplifies to
> O(n + k log n), and if k is close to n, it simplifies to
> O(n log n + k).

Ian Lynagh wrote:
> Hmm, is something wrong with the following?:
> [...]
> Total: O(n + k log k)

Mh, I'm not sure. At least, we have

log (n! / (n-k)!)
= log n! - log (n-k)!
=  log 1 + log 2 + log 3 + ... + log (n-k) + ... + log n
- log 1 - log 2 - log 3 - ... - log (n-k)
= log (n-k +1) + ... + log (n-k +k)

which is greater than (k log (n-k)) and smaller than (k log n). For k=1,
this estimate yields a minimum time of (log n) to find the minimum of a
list. While not wrong, this clearly underestimates the necessary O(n).

I think that estimating (n log (n/(n-k)) to n for k << n is not correct
because the logarithm of 1 = n/n is 0 and not 1 :)

Ian Lynagh wrote:
> [1] http://en.wikipedia.org/wiki/Selection_algorithm

Thanks for the link, Ian. It clearly shows that a lazy

take k . qsort

takes only O(n + k log k) time. I posted an analysis as follow up to the