Which case of the master theorem is this recurrence?

Question

I have a question about the following recurrence relation:

$$T(n) = 27 \cdot T\left(\frac n 3\right ) + n^3 \log n$$

Using the master theorem, will this be

• $T(n) = \Theta(n^3)$, or
• $T(n) = \Theta(n^3 \log \log n)$?

Answer 1

If a recurrence relation is of the form

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

then, as per the Master Theorem, we have six conditions depending on value of $a,b,k$ and $p$

• If $\log_b a>k$ : Answer is $\Theta(n^{\log_b a})$
• If $\log_b a=k$ and $p>1$ : Answer is $\Theta({n^k}({\log n})^{p+1})$
• If $\log_b a=k$ and $p=1$ : Answer is $\Theta({n^k}\log\log n)$
• If $\log_b a=k$ and $p<1$ : Answer is $\Theta(n^k)$
• If $\log_b a<k$ and $p \geq 0$ : Answer is $\Theta({n^k}({\log n})^p)$
• If $\log_b a<k$ and $p < 0$ : Answer is $\Theta({n^k})$

In any problem, our main motive is to find $a,b,k$ and $p$.

For the problem with

• $a=27$
• $b=3$
• $k=3$
• $p=1$,

$\log_3 27 = 3$, so $\log_b a = k$, and since $p=1$, the answer is $\Theta({n^k}\log\log n)$

$$\Theta({n^3}\log\log n)$$

Answer 2

Quick check:

$$\Theta(n^3)=27\,\Theta\left(\frac{n^3}{27}\right)+n^3\log\log n$$

does not hold.