6
$\begingroup$

I need to analyze the time complexity of an online algorithm to keep track of minimum $K$ numbers from a stream of $R$ numbers. The algorithm is

  • Suppose the $i$th number in the stream is $S_i$.
  • Keep a max heap of size $K$.
  • If the heap contains fewer than $K$ elements, add $S_i$ to the heap.
  • Otherwise: if $S_i$ is smaller than the maximum element in the heap (i.e., the root of the heap), replace the root of the heap with $S_i$ and apply Max-Heapify to the heap; if $S_i$ is greater than or equal to the max element, do nothing.

The problem now is to find the expected number of times the Max Heapify operation will be called, when the stream of integers is of length $R$ and each element of the stream is (iid) uniformly distributed on $[1,N]$.

If the stream were guaranteed to contain only distinct elements, then the answer is easy:

$$E[X] = E[X_1] + E[X_2] + \dots + E[X_R],$$

where $X_i$ is the random indicator variable for occurrence of the Max Heapify operation at the $i$th number in the stream. Now

$$E[X_i] = \Pr[\text{$S_i$ is ranked $\le K$ among first $i$ elements}] = \min(K/i, 1).$$

Hence,

$$E[X] = K + K/(K+1) + \cdots + K/R.$$

That case is relatively easy. But how do we handle the case where the elements are iid uniformly distributed?

[This was actually a Google interview question.]

$\endgroup$
4
$\begingroup$

If the value of the $i$-th element is $x$, it causes a heapify, if and only if $j < K$ of the previous $i-1$ elements are smaller than $x$. This gives

$$E[X_i] = \frac{1}{N^i} \sum_{x=1}^N \sum_{j=0}^{K-1} c_{j,x},$$

where $c_{j,x}$ is the number of sequences of $i-1$ elements, of which exactly $j$ are smaller than $x$.

Now, to determine $c_{j,x}$, note that there are $\binom{i-1}{j}$ possibilities for the positions of the smaller elements in the sequence. For each of the smaller elements there are $x-1$ possibilities for its value, while for the larger or equal elements there are $N-x+1$ possibilities. This yields
$c_{j,x} = \binom{i-1}{j} (x-1)^j (N-x+1)^{i-1-j}$, and thus overall (after shifting $i$ and $x$ by $1$)

$$E[X] = \sum_{i=0}^{R-1}\frac{1}{N^{i+1}} \sum_{x=0}^{N-1} \sum_{j=0}^{K-1} \binom{i}{j} x^j (N-x)^{i-j}.$$

Unfortunately, all my attempts at bringing this formula into a simpler/closed form have been unsuccessful.

$\endgroup$
  • $\begingroup$ Can you please explain a bit more on how total number of ways in which $i$th element causes a heapify is given by $\sum_{x=1}^{N} \sum_{j=0}^{K-1} c_{j,x}$ $\endgroup$ – Piyush Feb 7 '14 at 7:54
  • $\begingroup$ @Piyush Does my edit make this clear? $\endgroup$ – FrankW Feb 7 '14 at 12:37
1
$\begingroup$

It depends on the histogram of the elements. Consider for example the other extreme case, in which all the elements are the same. Instead of $K\log \tfrac{R}{K}$ (not $K+K\log \tfrac{R}{K}$ like you wrote) you get $0$. (The additive discrepancy of $K$ results from the fact that according to your description of the algorithm, in the first $K$ steps there is no heapifying.)

$\endgroup$
  • $\begingroup$ Agreed,for the extreme case we get 0. But we are concerned with the expected numbers of times the function will be called, i.e average of all possibilities, that is how most of the algorithms are analyzed. $\endgroup$ – Piyush Sep 29 '13 at 8:41
  • 1
    $\begingroup$ It depends on your model, then: what distribution the numbers are drawn from. For example, if it is a continuous distribution, then the probability of having two identical elements is zero. If the numbers are random 64-bit numbers, then the probability is practically zero. What distributions do you have in mind? Do you want an answer for an arbitrary distribution? $\endgroup$ – Yuval Filmus Sep 29 '13 at 23:54
  • $\begingroup$ Sorry for not mentioning this explicitly, the numbers are simply integers belonging to range $[1,N]$. $\endgroup$ – Piyush Sep 30 '13 at 20:47
  • 1
    $\begingroup$ This is not a distribution. Are they uniform integers from $1$ to $N$? $\endgroup$ – Yuval Filmus Oct 1 '13 at 1:13
  • $\begingroup$ Yeah they are, each number is equally likely to be picked at each instance. $\endgroup$ – Piyush Oct 1 '13 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.