3 ms·
IMO, most of these explanations of Big O that I've ever seen have missed the key feature of Big O (the "killer application" if you will): that it's relatively i
by pmiller2 13y ago
IMO, most of these explanations of Big O that I've ever seen have missed the key feature of Big O (the "killer application" if you will): that it's relatively independent of the exact computational model you use. Sure, you have to decide on the broad strokes of your computational model, but you don't need exact, instruction-level details.
This is a pretty huge benefit because it means every CS paper doesn't have to start with a section introducing an abstract machine. The downfall is, of course, that you lose some ability to estimate the potential real-world performance of the algorithm, and the notation itself hides differences between algorithms of the same Big O complexity.
- sesqu 13y agoThat's not a feature of O; that's simply a feature of leaving stuff out. O is a simplification of a function, but says nothing about how to construct the function. You need to have your (implicit) computational model before you can start counting critical operations, whether you describe it or not. This is actually somewhat important, since almost everyone has agreed on a model that, among other things, considers random access, multiplication, hashing, and even explicitly O(log log n) operations to take constant time. It's one of the many reasons why people make incorrect proofs about P=?NP. edit: If you meant that the simplification abstracts away implementation details like 3n^2+42 vs 2n^2+n, you're right, that's valuable. But I still argue that you ascribe it too much value when it comes to underspecifying your computational model.
- dionyziz 13y agoHow about this one? http://discrete.gr/complexity/ http://discrete.gr/complexity/ And if you don't like it, you can edit it too: https://github.com/dionyziz/complexity-article https://github.com/dionyziz/complexity-article
- VLM 13y agoThats a good point, but I've always found the killer app for big O notation is something the answer claims is wrong impossible: "You can't compare an algorithm to do arithmetic multiplication to an algorithm that sorts a list of integers." I rarely if ever implement just a multiplier or just a sorter. I end up implementing systems. And if everything in the system is linear or small poly but step #7 is exponential, then comparing Big O for unrelated algos is extremely valuable for me to estimate how long the overall system is going to take and where optimization effort should be placed for best improvement, etc. Don't waste time on making something linear a little faster, when I could be trying to refactor something exponential into something merely poly, somehow (assuming its even theoretically possible per some big O evaluation). Or refactor the whole system to be only poly.