9 ms·
Yup. Achieving a better big-O could for example be the difference between something being possible or not, whereas fine-tuning an algo without altering its big-
by _greim_ 10y ago
Yup. Achieving a better big-O could for example be the difference between something being possible or not, whereas fine-tuning an algo without altering its big-O might be the difference between needing five servers or ten. Still relevant, but a different class of relevance.
- FreeFull 10y agoIt can also be the case that an algorithm with a worse big-O complexity might actually be better because all your inputs are small and the constant multiplier is lower than the more complicated, better big-O algorithm
- stouset 10y agoThis suggestion gets trotted out in every discussion on Big-O. In 16 years of doing this professionally, I have not once encountered a situation where that would have been relevant. Any case where it even remotely might have been, the algorithm wouldn't have been hot enough to warrant considering it at all.
- FreeFull 10y agoOne example would be multiplying large matrices together. A common algorithm used is https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm with a big-O complexity of around O(n^2.8074). https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a... has a complexity of around O(n^2.375477), but the constant factors are so large it is currently never better to use it over the Strassen algorithm.