# Which case of the master theorem is this recurrence?

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)$$?
• Plug the possible answers in the recurrence, and you'll know.
– user16034
Commented May 18, 2022 at 8:19

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 and $$p \geq 0$$ : Answer is $$\Theta({n^k}({\log n})^p)$$
• If $$\log_b a 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)$$

• Please don't revert back changes that actually fix math notation. 1. It's $\Theta(\cdot)$ and not $\theta(\cdot)$. 2. It's $\log$ not $log$. 3. Don't use \bigg when \left will do. 4. $p = 1$, not $p = -1$. Commented Sep 21, 2021 at 9:39
• Thanks for the information @PålGD. Wasn't aware of these. Commented Sep 21, 2021 at 9:48

Quick check:

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

does not hold.