Big O notation is horrible when comparing algorithms.
I realize this is going against 30+ years of established programming rules, but the fact is that I've never found BigO notation to be that useful because of the amount of data it doesn't describe.
Why? BigO only works when we assume that the running time per element is constant across all data structures. In addition, it assumes that data structures / algorithms don't incur 'unknown' performance burdens. In REAL programming, both of these concepts are incorrect; Sparse traversal data structures, which may be faster due to lookup times etc, can incur additional hardware burdens (such as cache misses, branch mis-prediction, and pointer chasing) that aren't listed in your general O(n log n) evaluation.
In addition, BigO notation doesn't give any suggestion towards the millions of other issues around selecting a given algorithm, like memory consumption, or setup time (which the ps3 devs really care about!) .
What do I use then? Personally, I came up with something else :
The more I program, the more I realize that every algorithm is a trade-off. You are always pushing/pulling/compromising and trying to fight the caveats at the same time.
I find that the Triangle makes a much better discussion measure, as you can easily bounce things around and evaluate what REALLY matters.
In addition to that, any given algorithm is usually a sum of it's parts, meaning that you may need to create sub sections that lean more one way than the other in order to get the entire algorithm skewed towards one point on the pyramid.
For instance, computing all floating point values at run time between [0,1] can be done, but you'll loose performance for it. Where as moving towards a LUT increases memory footprint, decreases quality, but massively increases performance.
Another great example is mip-mapping. In order to increase performance, we decrease texture quality by introducing more mip values. Effectively, we've moved the point in our triangle from the quality side, closer to the middle, where performance increases, and so does memory consumption.
Finding an algorithm that pins right into the middle of this pyramid is usually pretty difficult, and more importantly UNDESIRABLE to find. Specifically, putting an algorithm right in the middle is something you don't want to do, because every algorithm always has a trade off. You need to know where you can squeeze out 10% more performance, or memory. Which is another reason I prefer the triangle; It allows you to see where you COULD go, and more importantly, what SPACE your algorithm can improve in during periods where you need to increase in any given dimension.
As a graphics programmer, I'm always worried about these three factors when writing an algorithm, especially if you're about to ship on a console, or other embedded memory system, in which case the trade offs between performance, memory, and quality are MUCH worse.
Think it's crazy? Give it a try, and I'm confident you'll find that as a programmer, it's much more natural to think in terms of a triangle than an O.
That's what she said.
~Main
