5
$\begingroup$

Suppose that we have $ \\ T(n)=\left\{\begin{matrix} c, & \ \text{if } n<d\\ aT\left( \frac{n}{b} \right )+f(n), & \ \ \text{if } n \geq d \end{matrix}\right.$

The Master theorem is the following:

  1. If $f(n)=O(n^{\log_b a- \epsilon})$, then $T(n)= \Theta(n^{\log_ba})$

  2. If $f(n)= \Theta(n^{\log_b a} \log^k n)$, then $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$

  3. If $f(n)=\Omega(n^{\log_b a+ \epsilon})$, then $T(n)= \Theta(f(n))$, provides $af\left(\frac{n}{b} \right) \leq \delta f(n)$ for some $\delta<1$ for all $n \geq d$.

Proof:

Using iterative substitution, let us see if we can find a pattern:

$$T(n)=aT\left( \frac{n}{b}\right)+f(n)=a \left(aT \left(\frac{n}{b^2} \right) +f\left( \frac{n}{b}\right)\right)+f(n)= \dots\\= a^{\log_bn}T(1)+ \sum_{i=0}^{(\log_bn)-1} a^i f\left( \frac{n}{b^i} \right)=n^{\log_b a} T(1)+ \sum_{i=0}^{(\log_b n)-1} a^i f\left(\frac{n}{b^i} \right)$$

We then distinguish the three cases as

  • The first term is dominant
  • Each part of the summation is equally dominant
  • The summation is a geometric series

Don't we have to explain further which case correponds to which of the following cases

  • The first term is dominant.
  • Each part of the summation is equally dominant.
  • The summation is a geometric series

and justify why it is like that? How could we justify it?

$\endgroup$
  • 1
    $\begingroup$ I can't tell what your question is. Are you saying you don't understand a proof you've read? Or that you don't think it's correct? You are definitely skipping a) some assumptions, b) the proof of the pattern by induction and c) applying the case assumptions to the solution for simplification. $\endgroup$ – Raphael Jun 7 '15 at 12:15
  • $\begingroup$ I have understood the proof but I am trying to relate the last three cases of the proof with the three cases of the Master Theorem.Can can we explain further that when the first term is dominant, we have the first case of the Master Theorem and so on..? @Raphael $\endgroup$ – Mary Star Jun 7 '15 at 12:30
  • 1
    $\begingroup$ the 3 "hints" are not (separate) cases but simultaneous properties that lead to the proof. $\endgroup$ – vzn Jun 7 '15 at 15:37
  • 1
    $\begingroup$ Is this the complete "proof"? It's just a proof sketch. Presumably you can make the connection to the three cases in the statement of the theorem yourself (they should be presented in the same order). $\endgroup$ – Yuval Filmus Jun 8 '15 at 0:43
1
$\begingroup$

The three cases correspond exactly to the three cases in the statement of the theorem. Let's consider them one by one. Suppose for simplicity that $T(1) = 1$.

Case 1. Suppose that $f(n) = n^\delta$, where $\delta < \log_b a$. Then $$ T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^\delta. $$ Since $\delta < \log_b a$, we have $b^\delta < a$ and so $a/b^\delta > 1$. Therefore $$ \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i = \left(\frac{a}{b^\delta}\right)^{\log_b n} \sum_{j=1}^{\log_b n} \left(\frac{b^\delta}{a}\right)^j = \Theta(n^{\log_b a - \delta}), $$ since the geometric series $\sum_j (b^\delta/a)^j$ converges, and $\log_b (a/b^\delta) = \log_b a - \delta$. We conclude that $$ T(n) = n^{\log_b a} + \Theta(n^{\log_b a - \delta} n^\delta) = \Theta(n^{\log_b a}). $$ (So it is not quite true that the first term is dominant.)

Case 2. Suppose that $f(n) = n^{\log_b a}$ (this is the case $k = 0$; the case $k > 0$ is similar though slightly more complicated). Then $$ T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^{\log_b a}. $$ This time $a = b^\delta$, and so each summand is equally dominant, leading to $$ T(n) = n^{\log_b a} + (\log_b n) n^{\log_b a} = \Theta(n^{\log_b a} \log n). $$

Case 3. Suppose that $f(n) = n^\delta$, where $\delta > \log_b a$. Then $$ T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^\delta. $$ Since $\delta > \log_b a$, we have $b^\delta > a$, and so $a/b^\delta < 1$. Therefore the geometric series $\sum_i (a/b^\delta)^i$ converges, implying that $$ T(n) = n^{\log_b a} + \Theta(n^\delta) = \Theta(n^\delta). $$


These proof sketches serve to explain that proof hints. However, they're not a complete proof, for two reasons. First, I assumed that $f$ has a specified form rather than a specified order of magnitude. Second, there is a tacit assumption that $n$ is a power of $b$. With more work we can take these points into account and prove the complete theorem. (A third and more minor point is the base case – you have assumed a base case of $1$, whereas the theorem calls for an arbitrary base case.)

$\endgroup$

Your Answer

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

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