News for hackers. Stuff that matters.
Re:My Favorite Algorithm: Linear Time Median Finding by Aardwolf on Thursday July 25, 2024 @08:06AM (#41067642)
> No, it's O(N+M) where N is the number of strings and M is the sum of the lengths of the strings.

That would mean it's possible to sort N random 64-bit integers in O(N+M) which is just O(N) with a constant factor of 9 (if taking the length in bytes) or 65 (if taking the length in bits), so sort billions of random integers in linear time, is that truly right?

Re:My Favorite Algorithm: Linear Time Median Finding by anonymoushn on Thursday July 25, 2024 @08:26AM (#41067824)
> That would mean it's possible to sort N random 64-bit integers in O(N+M) which is just O(N) with a constant factor of 9 (if taking the length in bytes) or 65 (if taking the length in bits), so sort billions of random integers in linear time, is that truly right?

Yes. You can sort just about anything in linear time.

> EDIT: I think it does make sense, M is length*N, and in scenarios where this matters this length will be in the order of log(N) anyway so it's still NlogN-sh.

I mainly wrote N+M rather than M to be pedantically correct for degenerate inputs that consist of mostly empty strings. Regardless, if you consider the size of the whole input, it's linear in that.

Re:My Favorite Algorithm: Linear Time Median Finding by exDM69 on Thursday July 25, 2024 @09:09AM (#41068256)
Yes, radix sort can sort integers in linear O(N) time.