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

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top