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...

▲

gpderetta 2 days ago | parent [-]

Interesting, after the mention of inverse Ackerman and spanning trees, I was sure this was going to be Union-Find (i.e. Kruskal's)!

	▲	eru a day ago \| parent [-]
		No, it's based on soft heaps. A remarkable data structure that I recently used to prove that you can simulate a priority queue in linear time. By simulate I mean: You get a sequence of instructions like 'insert x' and 'delete minimum', and you want to know what's elements are left in your priority queue at the end; but you don't care about any intermediate state. It turns out that even in the comparison model, you can answer this question in linear time in the worst case. Precisely, with no approximation.