1
$\begingroup$

What I'm taught in my class -

$T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$
where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number.

  1. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$
  2. if $a=b^k$ then,
    • if $p>-1$, then $T(n)=\theta(n^{\log_ab}\log^{p+1}n)$
    • if $p = -1$, then $T(n)=\theta(n^{\log_ab}\log\log n)$
    • if $p<-1$, then $T(n)=\theta(n^{\log_ab})$
  3. if $a<b^k$, then
    • if $p\geq 0$, then $T(n)=\theta(n^k\log^pn)$
    • if $p<0$, then $T(n)=O(n^k)$

On certain websites, the above representation for Master Theorem is slightly different as follows -

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

This ambiguity creates a great confusion while solving problems such as :

What is the value of the recurrence : $T(n)=T(\sqrt{n})+\theta(\log\log n)$

Substituting $n=2^m$, we get a new expression :

$S(m)=S(\frac{m}{2})+\theta(\log m)$
Here $a=1$, $b=2$, $k=0$ and $p=1$

If I apply Master Theorem as per the way I am taught in class, the result I get is :

$T(n)=\theta(\log\log\log n)$

and if I solve using the other formula, I get the result as :

$T(n)=\theta((\log\log n)^2)$

Which is the correct one? This confusion is making me question every problem that I've solved.

$\endgroup$
  • 2
    $\begingroup$ By convention, the notation $log^p(x)$ is defined to be $(log(x))^p$, not $p$ iterations of the $log$ function. This is similar to the trigonometric functions, which gives us identities like $sin^2(x) + cos^2(x) =1$. $\endgroup$ – mhum Dec 19 '14 at 22:38
  • $\begingroup$ That was just the explanation I needed. $\endgroup$ – Siddharth Thevaril Dec 19 '14 at 22:48
  • $\begingroup$ @mhum Make an answer? $\endgroup$ – Yuval Filmus Dec 19 '14 at 23:36
6
$\begingroup$

By convention, the notation $log^p(x)$ is defined to be $(log(x))^p$, not $p$ iterations of the $log$ function. This is similar to the trigonometric functions, which gives us identities like $sin^2(x)+cos^2(x)=1$.

$\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.