[EMAIL PROTECTED] 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 _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe