# Why in BFPRT (median of medians) algorithm the partition of the array by $7$ blocks would work but with the $3$ fail?

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)$$?

Let's take a look at the case of size 7 first. Here, we want to show a linear upper bound for $$T(n)$$. Thus, we choose the recurrence relation $$T(n) \leq T(n / 7) + T(5 / 7 n) + dn$$ (remember, it is an upper bound). We guess that the solution is of the form $$T(n) \leq cn$$ for some constant $$c$$ and prove it with induction: $$T(n) \leq T(n / 7) + T(5 / 7 \cdot n) + dn \leq c \cdot n/7 + c \cdot 5/7 \cdot n + dn = 6/7 \cdot cn +dn.$$ To this end, we choose $$c = 7 d$$, resulting in $$T(n) \leq cn$$.
Now we want to show a lower bound for size 3 (for the worst-case, tho!). So we have find a lower bound for its recurrence equation, namely: $$T(n) \geq T(n/3) + T(2/3 \cdot n) + dn .$$ The list of medians takes $$T(n/3)$$ since there are $$n/3$$ medians (resp. blocks). In the worst case, we have to recursively search in an area of size at least $$2/3 n$$. Clearly, this recurrence relation is not linear. To get an intuition for this, imagine that we would have equality. Assuming a solution of the form $$T(n) = cn$$, we get $$T(n) = 1/3 \dot cn + 2/3 \dot cn + dn$$. Since $$d>0$$, $$T(n) > cn$$ which contradicts our assumption.
The key part is that for block size $$3$$ the sizes of the recursive calls add up to $$n$$, which does not help to reduce the running time.