Timeline for Data structure with search, insert and delete in amortised time $O(1)$?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 7, 2013 at 4:27 | comment | added | A T | @JeffE and Raphael; please review my other answer and confirm/deny my result when you get the chance. Thanks. | |
| May 21, 2012 at 17:51 | comment | added | JeffE | @AT: The sorting lower bound was proved in a much weaker model of computation, namely binary decision trees. The bound was "proved wrong" by developing faster algorithms that cannot be described as binary decision trees. In order to prove Fredman and Saks' lower bound wrong, you'll have to design a faster algorithm that doesn't access memory. Best of luck. | |
| May 21, 2012 at 15:22 | comment | added | Raphael | @AT: That bound was never "proved wrong". There are situations where it does not apply, but that is an entirely different statement! | |
| May 21, 2012 at 12:45 | vote | accept | A T | ||
| Jan 6, 2013 at 17:55 | |||||
| May 21, 2012 at 9:22 | history | answered | JeffE | CC BY-SA 3.0 |