You're doing it wrong: B-heap 10x faster than binary heap (2010)
I guess it is that season again ? :-)<p>This article seems to pop up about every other year, and pretty much garner the same general reactions every time.<p>A lot of CS-majors immediately go in to defensive mode, starting to spew O(blablabla) formulas while thumbing their text-books.<p>That actually just underscores the main point I tried to communicate in that article:  CS education simplified the computing platform used for algorithmic analysis so much that it has (almost) lost relevance.<p>The big-O has little to do with real-world performance any more, because of the layers of caching and mapping going on.  In practice O(n²) can easily be faster than O(n) for all relevant n, entirely depending on ordering of access in the implementation.<p>Also, CS-education tends to gloss over important footnotes.  Take quicksorts worst-case performance, which even wikipedia describes as "rare".  It is not.  Sorted data are very, very common.<p>Originally researchers were more careful about these issues, and they operated with several distinct big-O's.  Re-read TAoCP about sorting on tape-drives for a classic example.<p>Some pull out "Cache-Oblivious Algorithms", usually having never actually tried to implement, benchmark or use any of them.<p>They are, as a rule, horribly complex, and seldom faster in practice, because they hide a very large performance constant in their complexity.<p>More often than not, there are no available reference implementation, so people cannot easily try them out, and none of them are fast enough to compensate of the embuggerance of the software patents which cover them.<p>There are usually one or two who claim that "Virtual Memory" is no longer a relevant concern and that one should just put "enough RAM" in the machine.<p>Throwing hardware at the problem is a nice job if you can get it, and a nice hobby if you can afford it.<p>However, even if the money is there, what about the energy consumption ?<p>Our climate is rapidly deteriorating because of greenhouse gasses from our energy-production, and more and more algorithms run on battery-power.<p>If I were writing a CS-thesis or CS-textbook today, it would be all about big-E() notation, and how it only weakly correlates with big-O() notation.