0

How can I solve this problem with master theorem. Giving asymptotic upper and lower bounds

If

$T(n)=4T(n/3)+ n log(n)$

a=4 b=3 k=1

for the formula $aT(n/b)+n^k log^b(n)$

if $a>b^k$ then $T(n)=\theta(n^{log_b^a})$ which is

then does this mean the upper and lower bound is

$=\theta(n^{log_3^{4}})$

Would this be correct I am not good at these types of problem they are.. too abstract.

Fernando Martinez
  • 6,698
  • 19
  • 74
  • 108

1 Answers1

1

The first case you need to analyze is: Is $n\log(n)=O(n^{c})$ where $c<\log_{3}(4)$? $\log_{3}(4)$ is a little bigger than $1$, so you can take $c>1$... say $c=1+\epsilon$ for a fixed small $\epsilon$. If $n\log(n)=O(n^{1+\epsilon})$--which it is, I'll leave it to you to justify that step--then by the result is that $T(n)=\Theta(n^{\log_{3}(4)})$.

This all comes from https://en.wikipedia.org/wiki/Master_theorem#Case_1

TravisJ
  • 7,426