On Fri, Apr 13, 2007 at 07:32:20AM -0400, [EMAIL PROTECTED] wrote: > > Quoting Thomas Hartman <[EMAIL PROTECTED]>: > > > Does that mean you can have the k minima in O(n) time, where n is > > length of list, which would seem to be an improvement? > > It's worth considering what the theoretical minimum is. > > 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).
Hmm, is something wrong with the following?: Tuple each element with its position: O(n) Find kth smallest element in linear time, as per [1]: O(n) Filter list for elements <= kth smallest: O(n) Sort filtered list by position: O(k log k) map snd to get the positions: O(k) Total: O(n + k log k) (the filter step will take care of elements with the same value as the kth smallest, as the filter is also comparing element positions when the values are the same). Thanks Ian [1] http://en.wikipedia.org/wiki/Selection_algorithm _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
