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


1 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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.