4 ms·
I 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 t
by onan_barbarian 16y ago
I 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 16y 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.