28 ms·

When you were in class, where you ever even introduced to the concept that sometimes it might be possible that O() notation might not tell the whole truth? I un

by drfugly 16y ago

When you were in class, where you ever even introduced to the concept that sometimes it might be possible that O() notation might not tell the whole truth? I understand that for the most part you shouldn't have to worry about it, but shouldn't we still warn students about this?

kd0amg 16y ago
Do you mean something like the case of quicksort mentioned in the post?[1] I was taught average- and best-case analysis along with worst-case analysis. Or do you mean some other fact not revealed by that analysis? [1] "Quicksort is a magical algorithm that theory tells us runs in O(n^2)"
- drfugly 16y ago
  Right, but there is also the cases where a nlg(n) quicksort for the most part is slower than the O(n^2) version in the real world. I wonder if current CS teaching is completely ignoring real-word performance.
seancron 16y ago
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?
- drfugly 16y ago
  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.
- Someone 16y ago
  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.
moxiemk1 16y ago
Absolutely! I suppose when I speak of asymptotic analysis, I'm including average case/expected case/degenerate case analysis in the whole exercise. Perhaps "runtime analysis" is a better term - it can then incorporate latency analysis as well. But yes, that was integal to the treatment of the subject. I remember having to determine what the worst-case of quicksort looks like as a part of an assignment to exhibit, in practice, best/average/worst case runtime of a number of sorts - and this was an freshman-level intro course. That particular problem was one of the most fun homeworks I've ever had - a rather satisfying solution.
- baddox 16y ago
  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.
  - thwarted 16y ago
    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).
anonymoushn 16y ago
Yes, a few professors discussed situations in which a theoretically slower algorithm was better in almost all real situations, and situations like timsort in which it is best to fall back on an asymptotically slow algorithm when your inputs are very small.
baddox 16y ago
We were taught what big O notation actually is, so yes. The whole point of big O notation, what makes it so useful, is that it hides information (namely constant factors). It's not supposed to "tell the whole truth," it's supposed to allow the analysis of algorithms not at any one runtime, but in an asymptotic mindset. With big O notation, you're not interested in how fast an algorithm ever actually runs (for that is the realm of constant factors), but rather how its running time changes as the size of its input changes.

by drfugly 16y ago

kd0amg 16y ago

Do you mean something like the case of quicksort mentioned in the post?[1] I was taught average- and best-case analysis along with worst-case analysis. Or do you mean some other fact not revealed by that analysis? [1] "Quicksort is a magical algorithm that theory tells us runs in O(n^2)"

drfugly 16y ago
Right, but there is also the cases where a nlg(n) quicksort for the most part is slower than the O(n^2) version in the real world. I wonder if current CS teaching is completely ignoring real-word performance.

seancron 16y ago

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?

drfugly 16y ago
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.
Someone 16y ago
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.

moxiemk1 16y ago

Absolutely! I suppose when I speak of asymptotic analysis, I'm including average case/expected case/degenerate case analysis in the whole exercise. Perhaps "runtime analysis" is a better term - it can then incorporate latency analysis as well. But yes, that was integal to the treatment of the subject. I remember having to determine what the worst-case of quicksort looks like as a part of an assignment to exhibit, in practice, best/average/worst case runtime of a number of sorts - and this was an freshman-level intro course. That particular problem was one of the most fun homeworks I've ever had - a rather satisfying solution.

baddox 16y ago
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.
- thwarted 16y ago
  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).

anonymoushn 16y ago

Yes, a few professors discussed situations in which a theoretically slower algorithm was better in almost all real situations, and situations like timsort in which it is best to fall back on an asymptotically slow algorithm when your inputs are very small.

baddox 16y ago

We were taught what big O notation actually is, so yes. The whole point of big O notation, what makes it so useful, is that it hides information (namely constant factors). It's not supposed to "tell the whole truth," it's supposed to allow the analysis of algorithms not at any one runtime, but in an asymptotic mindset. With big O notation, you're not interested in how fast an algorithm ever actually runs (for that is the realm of constant factors), but rather how its running time changes as the size of its input changes.