News for hackers. Stuff that matters.
Re:My Favorite Algorithm: Linear Time Median Finding by justinpombrio on Friday July 26, 2024 @02:05PM (#41080797)
I wasn't saying that you could get within 1% of the true median, I was saying you could find an element in the 49th to 51st percentile. In your example, the 49th percentile would be -90 and the 51st percentile would be 90, so the guarantee is that you would (with very high probability) find a number between -90 and 90.

That's a good point, though, that the 49th percentile and 51st percentile can be arbitrarily far from the median.

There are no comments on this comment yet.