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

Question

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

Answer 1

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.

For more information, check out the analysis on Wikipedia.

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.

If you have more questions, feel free to ask!