I am working with the median-median algorithm or BFPRT algorithm and I seek to understand why would the partition of the array by $ 7$ blocks would work but with the $ 3$ fail?
If we divide into blocks of $ 7$ then we will get: Solving it by substitution I think the following manner: It is a recursive tree. In the worst case it takes $ T(10n/14)$ time. So in the worst case it goes down to the bottom by $ (10/14)^kn=1$ steps; $ k=log_{14/10}n$ . At each level of recursive tree the total cost is $ \le cn$ for some constant $ c$ . So by the simplified assumptions using substitution $ k < n$ $ T(n)\le dn \log(n)$
$ T(n) \le T(n / 7) + T(10n / 14) + O(n) \le d\frac{n}{7}lg(n/7)+d\frac{10n}{14}lg(10n/14)+cn \le d(\frac{n}{7}lgn – \frac{n}{7}lg7) + d(\frac{10n}{14}lgn – \frac{10n}{14}lg10/14) + cn = d\frac{12n}{14}lgn – d\frac{n}{7}lg7 – d\frac{10n}{14}lg\frac{10}{14} + cn=d\frac{12n}{14}lgn – d\frac{n}{7}lg7 – d\frac{10n}{14}lg10 – d\frac{10n}{14}lg14 + cn \le d\frac{12n}{14}lgn + cn$
So, $ T(n) = O(nlgn)$
The same way for blocks of size $ 3$ .
$ T(n) \le T(n / 3) + T(2n / 3) + O(n)$ we get $ T(n) = O(nlgn)$
Now, how to show that $ T(n)$ for 7 is also $ O(n)$ and for 3 it can not be $ O(n)$ . Also, in general how can I guess that the $ T(n)$ is also $ O(n)$ because here in both cases my thoughts are they both $ O(nlogn)$ ?
