I have a equation: $T(n) = 4T(n/3) + n\ln n$
In this equation, I have to give tight asymptotic upper and lower bounds. What does that mean? I know I can apply Master theorem (which gives me theta notation) to this and according to me, this belongs to Case 1 because $n \ln n$ is $O(n^{1+\varepsilon})$. But how do I give the other bounds?
Thanks!
Best Answer
As you stated, you can apply Master theorem to get the $\Theta$ notation.
Master Theorem case 1:
For $T(n)=aT(\frac{n}{b})-f(n)$, if $f(n)=O(n^c)$ where $c<\log_ba$ then
$T(n)=\Theta (n^{\log_ba})$
Since in our case $a=4$, and $b=3$, we can calculate $\log_b a=log_3 4\approx1.261...>1.2$
So if we prove that $f(n)=n\log n=O(n^{1.2})$ then we have shown that it fits case 1 and we can infer $T(n)=\Theta(n^{\log_b a})=\Theta(n^{\log_3 4})$
Note that $\log(n)-n^{0.2}$ when $n=1000$ is negative. and it will be negative for every $n>1000$ as well. I leave this for you to proove.
So we can infer that for all $n>1000$, $n\log(n) < n^{1.2}$ which means $n\log(n)=O(n^{1.2})$
From master theorem, this means $T(n)=\Theta(n^{\log_3 4})$
The definition of $\Theta$ means that $T(n)=O(n^{\log_3 4})$ and also $T(n)=\Omega(n^{\log_3 4})$
So, $T(n)$ is not smaller than $n^{\log_3 4}$ when $n$ approaches infinity. But it is also not bigger than $n^{\log_3 4}$. So this is your tight boundary.
Intuitively speaking, you could say that $\Theta$ notation gives you an equivalence relation on the set of functions. For more information, see theta notation on http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations