I 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 s

I 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.