Timeline for Minimum space needed to sort a stream of integers
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:37 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Oct 30, 2012 at 12:58 | history | tweeted | twitter.com/#!/StackCompSci/status/263263613081513985 | ||
| Oct 25, 2012 at 8:23 | comment | added | Raphael | @Juho $\Theta$-bounds won't help to estimate whether we stay within constant memory. | |
| Oct 24, 2012 at 3:06 | vote | accept | Dave Tremont | ||
| Oct 22, 2012 at 23:15 | answer | added | Pedro | timeline score: 5 | |
| Oct 22, 2012 at 22:40 | comment | added | Dave Tremont | hmm don't think the question allows writing back to the input stream... | |
| Oct 22, 2012 at 19:53 | history | edited | Dave Tremont | CC BY-SA 3.0 |
added 1 characters in body
|
| Oct 22, 2012 at 19:48 | comment | added | Joe | Or is this question actually about buffered IO as in this blog post? (it might be, coming from SO). neopythonic.blogspot.com/2008/10/… | |
| Oct 22, 2012 at 19:45 | comment | added | Joe | The input is read-only and the output is write-only? Or are you allowed an intermediate "workspace" stream, that you can write to, and then read back from in the next round? | |
| Oct 22, 2012 at 19:42 | comment | added | A.Schulz | @Juho: Hmm, I am not sure if the lower bound of Munro and Paterson applies in this case. Their model is quite different from the scenario we have here. In particular we have a fixed universe. Maybe one could use ideas from integer data structures, however the space bound is very tight. | |
| Oct 22, 2012 at 19:31 | history | edited | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |
added 133 characters in body; edited tags
|
| Oct 22, 2012 at 18:32 | history | edited | Dave Tremont | CC BY-SA 3.0 |
edited body
|
| Oct 22, 2012 at 18:31 | review | First posts | |||
| Oct 25, 2012 at 8:23 | |||||
| Oct 22, 2012 at 18:22 | history | edited | Dave Tremont | CC BY-SA 3.0 |
deleted 7 characters in body
|
| Oct 22, 2012 at 18:13 | history | asked | Dave Tremont | CC BY-SA 3.0 |