2 ms·
Not particularly. I'll probably get downvoted but I'm not a huge fan of Big-O notation(hence the k). It's very hand-wavey about the things that have a signific
by vvanders 11y ago
Not particularly.
I'll probably get downvoted but I'm not a huge fan of Big-O notation(hence the k). It's very hand-wavey about the things that have a significant impact on performance(like cache misses).
Great from the ivory tower of academia but down in the real world we like things that run fast :).
- minimax 11y agoI agree with you and I meant it as a genuine complement.
- vvanders 11y agoThanks, I'll have to re-train my complement detector :). I enjoy breaking out Radix because it's one of those thing's that's so unintuitive when you come at it from a traditional CS perspective. AFAIK the only book I'm aware of that approaches data structures with a consideration for this type of performance is Real-Time Collision Detection(which is basically datastructures for 3D spatial domains).
- danking00 11y agoPerhaps you already know this, in which case I'm sorry for being pedantic. There are portions of the academy that also care about constant factors. They would write what, I think, you mean by O(kN) as k * N. If you need more precision, such as: "There's an order N term with constant factor k and some lower order terms whose constants I don't know (or don't care to calculate)", you could write that as: k * N + o(N). The little o means terms that grow strictly slower than N. Edit: formatting Edit2: I should have conceded that I'm not aware of anyone who attempts to use O-notation to talk about cache goodness. That certainly is swept under the covers of "Assume a perfect RAM machine" :P