Preferences

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
I 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 OP
Ok, 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
You 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.

This item has no comments currently.