3 ms·
Many results about unfeasibility of computer-based solutions to some problems were not known. For example the first important results about NP-hardness come fro
by praptak 15y ago
Many results about unfeasibility of computer-based solutions to some problems were not known. For example the first important results about NP-hardness come from the seventies.
I believe it wasn't even clear that the big O complexity is important in assessing how effective an algorithm is. This is pretty much obvious to us now (sometimes too obvious - there are some edge cases when the constant factor wins over the asymptotic complexity).
- scott_s 15y agoI agree with everything you said, except the parenthetical. I have difficulty considering matrix multiplication an "edge case," and I think that it's more common than you imply for us to choose algorithms with a higher asymptotic bound because of constant factors and architectural effects (mostly caching).
- praptak 15y agoOk, agreed about matrix multiplication and probably a few other problems, disagreeing about cache. You cannot really say that cache-aware algorithms have higher asymptotic bound. Some of them might happen to have below-optimal asymptotic bound in a cache-unaware memory model, which sort of misses the point of the algorithms being aware of cache.
- scott_s 15y agoYou cannot really say that cache-aware algorithms have higher asymptotic bound. Don't worry, I'm not. I'm saying that sometimes, naive algorithms have better cache behavior than more complicated algorithms with lower asymptotic bounds.