Hacker News Reader

Comment by minimax | Hacker News Reader

O(kN)

If this is trolling you're doing a very good job.

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 :).

Perhaps 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

I agree with you and I meant it as a genuine complement.

Thanks, 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).

If 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.

I 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_...

Radix 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.)

The 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.

There'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.

You 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).

Reply on news.ycombinator.com