1
$\begingroup$

Selecting the median as an approach for pivot selection halves the array into $T(\frac n3)$ and $T(\frac{2n}{3})$, so our $T(n)$ becomes:

$$T(n) = T(\frac{2n}{3})+ T(\frac n3)$$

Solution:

Approach 1: using master method, it's CASE 1 gives and upper bound:

$$ \begin{align} T(n) = T(\frac{2n}{3})+ T(\frac n3) + O(n)\\ \le 2 T(\frac{2n}{3})+ n\\ \le 2 T(\frac{n}{\frac 32})+ n\\ \vdots\\ =O(\log_{\frac 32}{2})\\ \\ \end{align} $$

Approach 2: using recursion tree, we sum up levels till we get:

$$\text{Level } k: \sum_{i=0}^k\binom ki \left(\frac{1}{3}\right)^{k-i}\left(\frac{2}{3}\right)^i = \left( \frac{1}{3} + \frac{2}{3} \right)^kcn$$

Since we have left subtree with $\frac n3$ doing less work than right subtree $\frac {2n}{3}$ as $\frac 32 > \frac 13$, we could derive a lower bound: for left subtree and an upper bound: for the right subtree. So, we could multiple each level on the right by $n$ to get $O(n\log_{\frac 32}{n})$ and similarily for lower bound.

Problem:

  • We get different upper bounds in approach 1 and approach 2, what do you think please?

Edit: case 1 in approach 1 one implies $O(n^{\log_{\frac 32}{2}})$.

$\endgroup$
7
  • 1
    $\begingroup$ Approach 1 is wrong. The master theorem doesn't imply that $T(n) = O(1)$ in your case. In fact, it doesn't apply at all to your recurrence. $\endgroup$ Oct 5 at 6:12
  • 1
    $\begingroup$ Also, you're using a difference recurrence in Approach 1 than in the prequel. $\endgroup$ Oct 5 at 6:14
  • $\begingroup$ @YuvalFilmus. Sorry for mistake. I meant $O(n^{\log_{\frac 32}{2}})$. So it's still has different answer from approach 2, what do you think please? $\endgroup$
    – Avra
    Oct 5 at 13:09
  • 1
    $\begingroup$ The recurrence can’t be solved using the master theorem, since it’s not of the correct form. $\endgroup$ Oct 5 at 14:18
  • 1
    $\begingroup$ Please be more explicit: Why&how would Median as pivot selection split the array into one third and two thirds (Why not into halves)? Does this refer to any particular implementation of partition? What exactly do the bounds discussed limit? $\endgroup$
    – greybeard
    Oct 5 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.