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
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 1, 2017 at 21:14 | vote | accept | Shahab_HK | ||
| Jan 1, 2017 at 19:28 | comment | added | orlp | Those are valid points. | |
| Jan 1, 2017 at 19:25 | comment | added | jbapple | 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. | |
| Jan 1, 2017 at 19:18 | comment | added | orlp |
+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.
|
|
| Jan 1, 2017 at 17:42 | history | answered | jbapple | CC BY-SA 3.0 |