1
$\begingroup$

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

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – Pål GD
    Sep 21, 2021 at 9:39
  • $\begingroup$ Thanks for the information @PålGD. Wasn't aware of these. $\endgroup$ Sep 21, 2021 at 9:48
0
$\begingroup$

Quick check:

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

does not hold.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.