1
$\begingroup$

I have learned the Master's Theorem from the CLRS textbook (2nd Edition), the form of the Master Theorem given in the above text is associated with the proof of each and every case. So at the end I know how it works and it also explains the intuition behind the same.

The form of Master Theorem given in CLRS is as follows:

(Master theorem) Let $a \geqslant 1$ and $b > 1$ be constants, let $f(n)$ be a function, and let $T (n)$ be defined on the nonnegative integers by the recurrence

$T(n) = aT(n/b)+ f (n)$ ;

where we interpret $n/b$ to mean either $\lceil b/n \rceil$ or $\lfloor b/n \rfloor$. Then $T(n)$ has the following asymptotic bounds:

  1. If $f(n)=O (n^{log_ba - \epsilon})$ for some constant $\epsilon > 0$, then $T(n)=\Theta (n^{log_ba})$.

  2. If $f(n)=\Theta (n^{log_ba})$, then $T(n)=\Theta (n^{log_ba}lg n)$

  3. If $f(n)=\Omega (n^{log_ba + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \leqslant cf(n)$ for some constant $c < 1$ and all sufficiently large n, then $T(n)=\Theta (f(n))$.

Now there is also a version of Master Theorem which is claimed as The Advanced Master Theorem by few sources on the web and also they claim that this version is more powerful than the one in the CLRS text.

$T(n) = aT(n/b)+\theta(n^{k}log^{p}n)$

where $n$ = size of the problem

$a$ = number of subproblems in the recursion and $a \geqslant 1$

$n/b$ = size of each subproblem

$b > 1 , k \geqslant 0$ and $p$ is a real number.

Then,

  1. if $a > b^{k}$, then $T(n) = θ(n^{log_ba})$

  2. if $a = b^{k}$, then

    • if $p > -1$, then $T(n) = θ(n^{log_ba} log^{p+1}n)$

    • if $p = -1$, then $T(n) = θ(n^{log_ba} log log n)$

    • if $p < -1$, then $T(n) = θ(n^{log_ba})$

  3. if $a < b^{k}$, then

    • if $p \geqslant 0$, then $T(n) = θ(n^{k} log^{p}n)$

    • if $p < 0$, then $T(n) = θ(n^{k})$

I could not find a text from where this has been taken, as a result I do not even know whether it is valid or not and without knowing its validity it shall be dangerous to apply it. If anyone has encountered the second version of the theorem, it shall be helpful if the name of the standard text book from which this second version has been given, is shared here. I want a proof of the second version of the Master Theorem if at all it exits and if so a one to one correspondence between the cases of the theorem given in the CLRS and that in the second version. Moreover the second version seems have used $\theta$ instead of $\Theta$ and if that is the case the second version only seems to cover case $2$ of the CLRS version which has $f(n) = \Theta(...)$

$\endgroup$
11
  • 1
    $\begingroup$ Have you consulted Wikipedia? $\endgroup$ – Yuval Filmus Jun 3 '20 at 21:58
  • 1
    $\begingroup$ There’s no difference between $\theta$ and $\Theta$. $\endgroup$ – Yuval Filmus Jun 4 '20 at 5:38
  • 1
    $\begingroup$ There is a paper of Chee Yap linked to on Wikipedia: cs.nyu.edu/exact/doc/master.pdf. Have you seen it? $\endgroup$ – Yuval Filmus Jun 4 '20 at 6:03
  • 1
    $\begingroup$ Also, you can typically derive the consequences of the master theorem from Akra–Bazzi. $\endgroup$ – Yuval Filmus Jun 4 '20 at 6:03
  • 1
    $\begingroup$ Actually, the link I gave is available from the SemanticScholar link, under "[PDF]" (next to the paywalled link). $\endgroup$ – Yuval Filmus Jun 4 '20 at 6:17

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.