Comment by cwillu
12 hours ago
Fun fact: Grover's algorithm is a rare example of an algorithm that was proven optimal before it was invented.
12 hours ago
Fun fact: Grover's algorithm is a rare example of an algorithm that was proven optimal before it was invented.
If you like this kind of thing: there's a deterministic algorithm for finding minimum spanning trees in a graph that's proven optimal, but no one knows its exact runtime.
Basically, the best they've proven is something like O(n * inverse_ackermann(n)), but it seems likely the algorithm actually runs in O(n). We also already have a randomised algorithm for this problem that runs in O(n) expected time on worst case input. The expectation is over the random choices.
https://en.wikipedia.org/wiki/Expected_linear_time_MST_algor...
Interesting, after the mention of inverse Ackerman and spanning trees, I was sure this was going to be Union-Find (i.e. Kruskal's)!