On 1/16/16 8:00 PM, Timon Gehr wrote:
On 01/16/2016 10:28 PM, Ivan Kazmenko wrote:On Saturday, 16 January 2016 at 15:25:50 UTC, Andrei Alexandrescu wrote:...To summarize: For k<<n we have O(n) average case and O(n log k) worst case. For k~n we have O(n log n) as HeapSort.The implementation falls back to topNHeap whenever k is within the first or last ~n/8 elements and therefore is Ω(n log n) on average.
Correct. The pedantic approach would be to only do that when k is up to log(n). -- Andrei
