# 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)$$?

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$. Sep 21 '21 at 9:39
• Thanks for the information @PålGD. Wasn't aware of these. Sep 21 '21 at 9:48