4 ms·
How do you prove that something is faster than everything else? Was it already running in linear-time? There aren't many non-trivial lower bounds out there, an
by Gehinnn 7y ago
How do you prove that something is faster than everything else? Was it already running in linear-time?
There aren't many non-trivial lower bounds out there, and I think they all use one of three ideas (diagonalization, crossing sequences or oracle reconstruction)!
- cperciva 7y agoSorry, I was unclear. I proved that my algorithm was faster than other known algorithms; I didn't prove that it was faster than all other possible algorithms.