4 ms·
Reading that was rather vindicating. The same concern is raised by phk in his B-heap essay [1], where he criticizes Knuth for the exact same reason -- that algo
by jallmann 12y ago
Reading that was rather vindicating. The same concern is raised by phk in his B-heap essay [1], where he criticizes Knuth for the exact same reason -- that algorithm analysis has become disconnected from the characteristics of the underlying hardware.
While phk has a point, the dig at Knuth's work feels a bit unfair. In any case, I'm curious to see whether future editions of TAOCP note this caveat in its analysis.
[1] http://queue.acm.org/detail.cfm?id=1814327 http://queue.acm.org/detail.cfm?id=1814327
- jamesmiller5 12y agoI believe tilde notation is meant to bridge the gap between a pure mathmatical behaviour analysis and realistic expectations when using an algorithm. Analysing an algorithm and determining that say for 2x input size expect 8x resource usage gives more information that would otherwise be hidden in big O notation. http://introcs.cs.princeton.edu/java/41analysis/ http://introcs.cs.princeton.edu/java/41analysis/
- Intermernet 12y agoThankyou, you in part answered my question elsewhere in this thread. I'll give it a read.
- neic 12y agoDo you know of any resources that teaches this? I'm looking for a hypothetical book like "CLRS for VMs".