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 1, 2017 at 21:14 | vote | accept | Shahab_HK | ||
| Jan 1, 2017 at 17:42 | answer | added | jbapple | timeline score: 16 | |
| Jan 1, 2017 at 16:59 | comment | added | Shahab_HK | @YuvalFilmus I googled the problem but any solution was in $O(nlogk)$ time... | |
| Jan 1, 2017 at 16:57 | comment | added | Shahab_HK | @YuvalFilmus yes, i've searched for an online algorithm. | |
| Jan 1, 2017 at 16:48 | comment | added | Shahab_HK | @xavierm02 it's not the selection problem identically. Because there is a memory limit constraint. | |
| Jan 1, 2017 at 16:13 | comment | added | Yuval Filmus | There are linear time in-place algorithms, which you can google, but they're somewhat complicated. | |
| Jan 1, 2017 at 15:12 | history | tweeted | twitter.com/StackCompSci/status/815576451311407104 | ||
| Jan 1, 2017 at 15:00 | comment | added | xavierm02 | It's called the selection problem en.wikipedia.org/wiki/Selection_algorithm | |
| Jan 1, 2017 at 14:55 | answer | added | orlp | timeline score: 3 | |
| Jan 1, 2017 at 14:00 | comment | added | Sarvottamananda | 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. | |
| Jan 1, 2017 at 11:16 | comment | added | Yuval Filmus | Are you interested in an online algorithm, or would any algorithm do? | |
| Jan 1, 2017 at 11:16 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
deleted 14 characters in body
|
| Jan 1, 2017 at 9:18 | history | edited | Shahab_HK | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Jan 1, 2017 at 9:04 | history | asked | Shahab_HK | CC BY-SA 3.0 |