Timeline for Finding k'th smallest element from a given sequence only with O(k) memory O(n) time
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 19, 2018 at 7:39 | history | edited | user12859 | CC BY-SA 3.0 |
changed wrong claim to what orlp meant
|
| Jan 4, 2017 at 7:08 | comment | added | user12859 | @orlp : I have asked a question about that on this site. | |
| Jan 2, 2017 at 6:42 | comment | added | orlp | @RickyDemer That's outside of the scope of this question, I can refer to the wikipedia articles for median of medians and introselect. | |
| Jan 2, 2017 at 5:15 | comment | added | user12859 | @orlp : How do you do the median-of-medians selection algorithm in O(log n) memory and O(n) time? | |
| Jan 1, 2017 at 19:16 | comment | added | orlp | @Shahab_HK It turns out I was wrong about believing $O(k)$ mem and $O(n)$ time didn't exist, see the other answer. | |
| Jan 1, 2017 at 18:05 | comment | added | orlp | @Shahab_HK I don't believe so, but $O(\log n)$ memory is so little it doesn't matter either way. In fact it's very rare $k < \log n$, and if I were given the choice even if $O(k)$ memory existed, I'd still chose $O(\log n)$. | |
| Jan 1, 2017 at 17:08 | comment | added | Shahab_HK | Thank you for your hints. So as i understand it, there is no algorithm yet which could do it in $O(k)$ memory and $O(n)$ time? | |
| Jan 1, 2017 at 16:05 | comment | added | orlp | @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. | |
| Jan 1, 2017 at 15:27 | comment | added | xavierm02 | $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)$. | |
| Jan 1, 2017 at 15:19 | comment | added | orlp | @xavierm02 That being said, it's still a nice speedup :) | |
| Jan 1, 2017 at 15:10 | comment | added | orlp | @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)$. | |
| Jan 1, 2017 at 15:04 | comment | added | xavierm02 | 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. | |
| Jan 1, 2017 at 15:01 | history | edited | orlp | CC BY-SA 3.0 |
added 53 characters in body
|
| Jan 1, 2017 at 14:55 | history | answered | orlp | CC BY-SA 3.0 |