Hacker News Reader

Could you explain what you mean a bit more by big O notation not telling the whole truth? Are you referring to the fact that algorithms that look the same in big O notation might have drastically different constants, which can affect real-world performance?

View on HN

It can be worse. A O(n log n) algorithm might be slower than a O(n^2) algorithm for all practical values of n.

Also, one should be careful what to count. Sorting strings, for example, is not quite O(n log n); average string length/expected offset of first difference/whatever should also be in that O().

Along the same line, for many algorithms, cache-locality is more important than number of CPU cycles. So, counting cache misses rather tha cycles can be the better way to judge an algorithm.

Yes, that's exactly what I'm getting at. Or cases where multithreading an application may look like it's going to bring obvious performance gain only to see the overhead kill your performance.

Reply on news.ycombinator.com