Timeline for Simple and practical deterministic algorithm, complicated running time
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17, 2010 at 20:53 | comment | added | Guilherme D. da Fonseca | I don't think the question is about a simple and practical algorithm with complex analysis. I think the question is about a simple and practical algorithm with complex running time, that is, the actual expression obtained for the upper bound. | |
| Nov 17, 2010 at 16:15 | comment | added | Neel Krishnaswami | The ratio of algorithm length to proof complexity for union-find is probably unbeatable -- all three operations are what, nine lines of code? | |
| Nov 17, 2010 at 8:26 | comment | added | Jukka Suomela | Well, $O(\alpha(n))$ time doesn't look that "complicated" if you compare it to $O(n^{4/3} \alpha(n) \log^2 n / \log \log n)$ in Guilherme's answer. :) | |
| Nov 16, 2010 at 23:58 | comment | added | Warren Schudy | Indeed, I posted the same answer but deleted it after I noticed you beat me to it. :) Simple and elegant algorithm that a non-theorist might even discover, but inverse Ackermann amortized complexity. | |
| Nov 16, 2010 at 23:43 | history | answered | Kevin Wortman | CC BY-SA 2.5 |