topN using a heap

[Andrei Alexandrescu via Digitalmars-d]

On 01/17/2016 06:41 AM, Ivan Kazmenko wrote:
> The average case is O(n + (k log n log k)) for small enough k. So, any k
> below roughly n / log^2 (n) makes the second summand less than the first.

I don't understand how you derived the average case complexity, and I 
don't understand how you derived the bound for k.

Regarding the complexity: for all k (small or large), it takes O(k) to 
build a heap. Then in the worst case we do (n - k) heap insertions, i.e. 
total complexity is O(k + (n - k) * log(k)). Is that correct?

If k is any fraction of n, the worst case complexity comes to O(n + n 
log n) i.e. O(n log n). By your calculation, the average complexity 
comes to O(n log^2 n), i.e. greater than the worst case. So there's a 
mistake somewhere.

Could you please clarify matters? Thanks!


Andrei