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.
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.