3 ms·
I take issue with this: "Line up elements in groups of five (this number 5 is not important, it could be e.g. 7 without changing the algorithm much)." The corr
by davidtgoldblatt 15y ago
I take issue with this: "Line up elements in groups of five (this number 5 is not important, it could be e.g. 7 without changing the algorithm much)."
The correct statement is that you can replace 5 with any larger number and the algorithm still works, but 5 is the least number you can pick here. That's the most interesting part of the algorithm to me - that "5" is connected to median-finding in the same way that "2" is connected to divide in conquer searching in a sorted array. But 2 is more obviously interesting than 5 (you can say "dividing something in 2 makes it smaller", but there aren't very many similar things you can say about 5).
- onan_barbarian 15y agoI may be having a durpy Saturday afternoon, but why is 3 not a valid choice for the group size? I am not saying 3 is a good number in a pragmatic sense, just that eyeballing the informal proof doesn't seem to yield any obvious problems with using groups of 3 for the desired result.
- dhruvbird 15y agoI haven't worked out the recurrence myself, but considering 3 as the partition size, we get the recurrence [1] (below). T(n) = T(n/3) + 4n/6 + O(n) __[1] It seems as if this doesn't workout to O(n) whereas if the middle term is 7n/10 (parition size = 5), it does work out.