Timeline for Worst known algorithm in terms of Big-O (more precisely Big-theta)?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 24, 2022 at 2:05 | comment | added | Ira Gessel | An updated link for "Pessimal Algorithms and Simplexity Analysis" by Andrei Broder and Jorge Stolfi is dl.acm.org/doi/10.1145/990534.990536. | |
| May 19, 2011 at 17:15 | comment | added | Joseph O'Rourke | See also CSTheory: "Polynomial-time algorithms with huge exponent" cstheory.stackexchange.com/questions/6660 | |
| May 19, 2011 at 14:34 | comment | added | Ira Gessel | See the paper "Pessimal Algorithms and Simplexity Analysis" by Andrei Broder and Jorge Stolfi, google.com/… | |
| May 19, 2011 at 13:09 | comment | added | Denis Serre | I really don't know much in this topic: The homotopy groups of spheres are calculable in finite time, but the complexity is so high that nobody could do in practice, even with the help of computers. | |
| May 19, 2011 at 12:34 | answer | added | Joel David Hamkins | timeline score: 8 | |
| May 19, 2011 at 12:00 | answer | added | Joseph O'Rourke | timeline score: 6 | |
| May 19, 2011 at 11:42 | comment | added | Someone | Algorithms calculating the diagonal of the Ackermann function tend to be slow. | |
| May 19, 2011 at 11:15 | comment | added | Peter Shor | @Gerry: you could ask the question: for what problem is the best running time given in the literature the maximum? | |
| May 19, 2011 at 10:35 | comment | added | Gerry Myerson | I'm not convinced this is a real question. Isn't it the case that given any algorithm one can find another that's significantly worse? | |
| May 19, 2011 at 10:26 | answer | added | user5810 | timeline score: 6 | |
| May 19, 2011 at 9:31 | comment | added | Mark | Bogosort! en.wikipedia.org/wiki/Bogosort | |
| May 19, 2011 at 9:22 | history | asked | Mike | CC BY-SA 3.0 |