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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Are you interested in an online algorithm, or would any algorithm do? $\endgroup$
    – Yuval Filmus
    Commented Jan 1, 2017 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$
    – Sarvottamananda
    Commented Jan 1, 2017 at 14:00
  • $\begingroup$ It's called the selection problem en.wikipedia.org/wiki/Selection_algorithm $\endgroup$
    – xavierm02
    Commented Jan 1, 2017 at 15:00
  • $\begingroup$ There are linear time in-place algorithms, which you can google, but they're somewhat complicated. $\endgroup$
    – Yuval Filmus
    Commented Jan 1, 2017 at 16:13
  • $\begingroup$ @xavierm02 it's not the selection problem identically. Because there is a memory limit constraint. $\endgroup$
    – Shahab_HK
    Commented Jan 1, 2017 at 16:48

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jan 1, 2017 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
    Commented Jan 1, 2017 at 19:25
  • $\begingroup$ Those are valid points. $\endgroup$
    – orlp
    Commented Jan 1, 2017 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$.

Improve this answer
$\endgroup$
11
  • $\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
    Commented Jan 1, 2017 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
    Commented Jan 1, 2017 at 15:10
  • $\begingroup$ @xavierm02 That being said, it's still a nice speedup :) $\endgroup$
    – orlp
    Commented Jan 1, 2017 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
    Commented Jan 1, 2017 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
    Commented Jan 1, 2017 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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