5 ms·
O(kN) If this is trolling you're doing a very good job.
by minimax 11y ago
O(kN)
If this is trolling you're doing a very good job.
- vvanders 11y agoNot 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
- gleenn 11y agoIf you're complaining because it's faster than O(N*log(N)), the fixed key size guarantees you'll never meet a sufficiently large N which is required when doing big-oh analysis. If you're complaining because of the k, k is the number of bits in the key and it's perfectly reasonable to have that spelled out explicitly.
- minimax 11y agoI wouldn't say it was a complaint but the k is definitely what caught my attention. https://en.wikipedia.org/wiki/Big_O_notation#Multiplication_by_a_constant https://en.wikipedia.org/wiki/Big_O_notation#Multiplication_...
- david-given 11y agoRadix sort really does have linear time complexity, but requires fixed size keys. If your keys are variable sized, e.g. strings, it's O(n log n) as usual. (I just looked it up on Wikipedia.)
- sirsar 11y agoThe three things to keep in mind about radix sort are A) It's noncomparative, while other sorting algorithms' performance is measured in number of comparisons, so there's a bit of apples-and-oranges going on. B) What is `k` for `n` unique keys? Log(n). So O(kn) is...? C) Despite those considerations, in practice radix sort can often outperform everything else, so use where appropriate.
- vvanders 11y agoThere's a 4th as well which is that the sort is stable on keys of the same value. So if you care about ordering(which a lot of rendering algorithms that use Radix do) it useful there as well.
- Jaxan 11y agoYou can sort strings also in linear time with a trie (for example). This requires O(n) time, where n is the total length of the input (i.e. sum of lengths of strings).