topN using a heap

[Ivan Kazmenko via Digitalmars-d]

On Sunday, 17 January 2016 at 16:06:31 UTC, Andrei Alexandrescu 
wrote:
> 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?

Yeah, I have the same notion.

> 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.

The upper bound O(n + k log k log n) is correct, but it's tight 
only for small k.  I'll explain below.

> Could you please clarify matters? Thanks!

Here is a more verbose version.

Suppose for simplicity that the array consists real numbers of 
the same continuous random distribution.
(A discrete random distribution would complicate the analysis a 
bit, since the probability of two elements being equal would 
become greater than zero.)
Then, element a_i is the minimum of a_1, a_2, ..., a_i with 
probability 1/i.
Moreover, it is the second minimum with probability 1/i, the 
third minimum with probability 1/i, ..., the maximum of a_1, a_2, 
..., a_i with the same probability 1/i.
To prove this, we can show that, if we look at the ordering 
permutation p_1, p_2, ..., p_i such that of a_{p_1} < a_{p_2} < 
... a_{p_i}, each of the i! possible permutations is equally 
probable.

What immediately follows is that when we track k smallest 
elements and consider element i>k, the probability that it will 
change the k smallest elements encountered so far is k/i.
Summing that for i from k+1 to n, we get the expected number of 
heap insertions:
(k/(k+1)) + (k/(k+2)) + ... + k/n.

Now, this is just k multiplied by:
(1/1 + 1/2 + 1/3 + ... + 1/n) *minus*
(1/1 + 1/2 + 1/3 + ... + 1/k).
As these are harmonic series, the first line is asymptotically 
equal to log n, and the second line asymptotically equal to log k.
To summarize, the expected number of heap insertions for an array 
of random reals is k (log n - log k), and the complexity is O(n + 
k log k (log n - log k)).

What I did here for simplicity is just omit the "minus logarithm 
of k" part to get an upper bound.
For small enough k, the bound is tight.
For example, when k=sqrt(n), log n - log k = log(n/k) = (log n) / 
2.
On the other hand, when k=Theta(n), log n - log k = log(n/k) = 
Theta(1).

Ivan Kazmenko.