ajb@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:
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