News for hackers. Stuff that matters.
Re:Should CS students be graded on performance? by baddox on Sunday March 06, 2011 @02:22AM (#2293703)
We talked about these things as well. I remember studying how to calculate the percentage of data sets of a given size that would bring out the worst-case running time of quick-sort.

Really, I think the issue with all the criticisms of asymptotic analysis is simply that too many people (even brilliant programmers and CS majors) just don't understand what big O notation actually means. If an algorithm is in, say, O(n lg n), that says nothing about how fast it runs with 10 inputs, 1,000 inputs, 1,000,000,000, etc. It merely says how its running time changes as its input size increases. 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.

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