Re:Should CS students be graded on performance?
by thwarted on Sunday March 06, 2011 @05:10AM
(#2293935)
The algorithm could literally take 1,000 years with an input size of 10. That doesn't matter. At some input size, it will run faster than a different algorithm in O(n^2) that completes in 1 millisecond with an input size of 10.
𝜪 is an indicator of work (number of steps) for a given n, not wall-clock time. This gets mildly confusing when you give each unit of work a value of 1 unit of time, and then talk about it in terms of time-like labels (seconds, hours, age of the universe).
I don't see that there's value is comparing an algorithm of n = "some input size" to another one with a different 𝜪 of n = 10. When comparing, you don't care about the value of n, you only care about how n changes the amount of work. When actually selecting and implementing, you care about n (because n will often be limited by something else, say available memory) -- if your n is small and pragmatically you know that even a terrible, brute-force algorithm will finish in a second, you use the one that is easier to implement and put an implementation specific limit on n (and you also put a TODO or FIXME on it with a comment that says if n ever needs to be increased, a different algorithm should be used).
𝜪 is an indicator of work (number of steps) for a given n, not wall-clock time. This gets mildly confusing when you give each unit of work a value of 1 unit of time, and then talk about it in terms of time-like labels (seconds, hours, age of the universe).
I don't see that there's value is comparing an algorithm of n = "some input size" to another one with a different 𝜪 of n = 10. When comparing, you don't care about the value of n, you only care about how n changes the amount of work. When actually selecting and implementing, you care about n (because n will often be limited by something else, say available memory) -- if your n is small and pragmatically you know that even a terrible, brute-force algorithm will finish in a second, you use the one that is easier to implement and put an implementation specific limit on n (and you also put a TODO or FIXME on it with a comment that says if n ever needs to be increased, a different algorithm should be used).