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

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.