3 ms·
You see this all over the place, e.g. cache-aware, SIMD-friendly approaches often win out over asymptotically better algorithms on real hardware for small to me
by the8472 7y ago
You see this all over the place, e.g. cache-aware, SIMD-friendly approaches often win out over asymptotically better algorithms on real hardware for small to medium problem sizes.
At large problem sizes a lot of effort has already been put into using the optimal algorithm. If simulations take days you're grateful for any constant factor improvements.
Asymptotic computational complexity does matter, but it only tells you how far you can push the problem. It tells you such things as "cracking this cipher is practically infeasible even if you turned the whole universe into a computer", "problem can only be approximated", "sometimes will not get a result at all" or "so ridiculously simple that we can run this on terabytes of data within minutes". But when you have taken all those categorical things into account and do an actual implementation then constant factors do matter in the same way that serving a website at 1Mbit/s vs. 100Mbit/s matters, even though it's only a constant factor reduction in load times.