Re:Should CS students be graded on performance?
by seancron on Sunday March 06, 2011 @01:26AM
(#2293629)
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?
[ Parent
| on HN ]
Re:Should CS students be graded on performance?
by Someone on Sunday March 06, 2011 @03:36AM
(#2293806)
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.