3 ms·
That table is so wrong it makes me mad.
by rawnlq 10y ago
That table is so wrong it makes me mad.
- teraflop 10y agoIn what way? Having skimmed it, I see a couple of minor mistakes but the bulk of it seems correct. The chart says you can search a Cartesian tree in O(log n) expected time, but I don't see how that's possible given that there's no ordering between a node's children. Also, it's possible to do mergesort in O(1) space; in fact, it's one of the exercises in TAOCP, if I recall correctly. But the algorithm is so complicated that nobody uses it in practice.