11
$\begingroup$

Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms of sequence and when get the $k+1$'th term, delete a term which we sure that it cannot be the $k$'th smallest element and then save $k+1$'th term. So we should have an indicator that shows this unusable term in each step and this indicator should be update in each step quickly. I began with "max"; but it cannot update quickly; Means that if we consider max then in first deletion we miss the max and we should search for max in $O(k)$ and its cause $(n-k)\times O(k)$ time that it's not linear. Maybe we should save first $k$ terms of sequence more intelligently.

How do I solve this problem?

$\endgroup$
  • 1
    $\begingroup$ Are you interested in an online algorithm, or would any algorithm do? $\endgroup$ – Yuval Filmus Jan 1 '17 at 11:16
  • $\begingroup$ If $k = \theta(n)$ then you can do it by using order statistics algorithm. If $k = o(n)$ then you can do it $O(k)$ memory and $O(n\log k)$ time using any height balanced trees. $\endgroup$ – Shreesh Jan 1 '17 at 14:00
  • $\begingroup$ It's called the selection problem en.wikipedia.org/wiki/Selection_algorithm $\endgroup$ – xavierm02 Jan 1 '17 at 15:00
  • $\begingroup$ There are linear time in-place algorithms, which you can google, but they're somewhat complicated. $\endgroup$ – Yuval Filmus Jan 1 '17 at 16:13
  • $\begingroup$ @xavierm02 it's not the selection problem identically. Because there is a memory limit constraint. $\endgroup$ – Shahab_HK Jan 1 '17 at 16:48
16
$\begingroup$

Create a buffer of size $2k$. Read in $2k$ elements from the array. Use a linear-time selection algorithm to partition the buffer so that the $k$ smallest elements are first; this takes $O(k)$ time. Now read in another $k$ items from your array into the buffer, replacing the $k$ largest items in the buffer, partition the buffer as before, and repeat.

This takes $O(k * n/k) = O(n)$ time and $O(k)$ space.

$\endgroup$
  • $\begingroup$ +1, this fits the asked asymptotics. That being said, I don't believe this is faster than doing a single linear-time selection algorithm... except when $k$ is a small constant, then it provides an interesting perspective. For example for $k = 1$ this algorithm produces the min function. $\endgroup$ – orlp Jan 1 '17 at 19:18
  • 1
    $\begingroup$ Sometimes, the linear-time selection algorithm uses too much space. For instance, it is not suitable for use in a streaming context or when the input array is immutable. $\endgroup$ – jbapple Jan 1 '17 at 19:25
  • $\begingroup$ Those are valid points. $\endgroup$ – orlp Jan 1 '17 at 19:28
3
$\begingroup$

You can do it in $O(k)$ memory and $O(n \log k)$ time by forming a fixed size max-heap from the first $k$ elements in $O(k)$ time, then iterating over the rest of the array and pushing a new element and then popping for $O(\log k)$ for every element giving total time $O(k + n\log k)$ = $O(n \log k)$.

You can do it in $O(\log n)$ auxiliary memory and $O(n)$ time by using the median-of-medians selection algorithm, selecting at $k$, and returning the first $k$ elements. With no change to asymptotics you can use introselect to speed up the average case. This is the canonical way to solve your problem.

Now technically $O(\log n)$ and $O(k)$ are incomparable. However I argue that $O(\log n)$ is better in practice, as it's effectively constant considering no computer system has more than $2^{64}$ bytes of memory, $\log 2^{64}= 64$. Meanwhile $k$ can grow to be as large as $n$.

$\endgroup$
  • $\begingroup$ Note that you can improve the complexity of the heap-based algorithm to $O(n \times \log\min (k, n - k))$ by reversing the order used by the heap when it's interesting. $\endgroup$ – xavierm02 Jan 1 '17 at 15:04
  • $\begingroup$ @xavierm02 $O(min(k, n-k))$ = $O(k)$. Proof: the worst case for $k$ is $n$. The worst case for $min(k, n-k)$ is $n \over 2$. They are the same within a constant factor, thus $O(min(k, n-k))$ = $O(k)$. $\endgroup$ – orlp Jan 1 '17 at 15:10
  • $\begingroup$ @xavierm02 That being said, it's still a nice speedup :) $\endgroup$ – orlp Jan 1 '17 at 15:19
  • $\begingroup$ $u_{n,k}=k$ is $O(k)$ but it's not $O(\min (k, n-k))$. Suppose it is. Then there is some $C$ and some $M$ so that for every $M\le k\le n$, we have $k\le C (n-k)$, which is clearly false (because we can take $n=k \to +\infty).$ So $O(\min(k, n-k))\subsetneq O(k)$. $\endgroup$ – xavierm02 Jan 1 '17 at 15:27
  • $\begingroup$ @xavierm02 I'm unfamiliar with your $u_{n, k}$ notation. To be fair, I'm in general quite unfamiliar with multidimensional big-$O$ notation, especially considering that dimensions $n, k$ are not unrelated. $\endgroup$ – orlp Jan 1 '17 at 16:05

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.