[Haskell-cafe] Re: k-minima in Haskell

[apfelmus]

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
old thread on haskell-general

  http://article.gmane.org/gmane.comp.lang.haskell.general/15110


Regards,
apfelmus