News for hackers. Stuff that matters.

A comment on My Favorite Algorithm: Linear Time Median Finding.

Re:My Favorite Algorithm: Linear Time Median Finding by SkiFire13 on Thursday July 25, 2024 @10:18AM (#41068962)
I wonder what's the reason of picking groups of 5 elements instead of 2 or 8.
[ Parent | on HN ]
Re:My Favorite Algorithm: Linear Time Median Finding by danlark on Thursday July 25, 2024 @10:33AM (#41069150)
3 and 4 elements will fail to prove the complexity is linear

You still can do 3 or 4 but with slight modifications

https://arxiv.org/abs/1409.3600

For example, for 4 elements, it's advised to take lower median for the first half and upper median for the second half. Then the complexity will be linear

[ Parent | on HN ]
Re:My Favorite Algorithm: Linear Time Median Finding by lalaland1125 on Thursday July 25, 2024 @10:24AM (#41069018)
1. You want an odd number so the median is the middle element of the sublist.

2. One and three are probably too small

[ Parent | on HN ]