How can $n \lg n = O(n^{log_3 4 - r})$?

How can I understand this bound, for me it is not true.

$$n\lg n = O(n^{\log_3 4 - r})$$

where $\lg n = \log_2 n$ and $r > 0$

I'm trying to solve this recurrence $T(n) = 4T(n/3) + n\lg n$ using the master method (used in algorithms analysis).

Solution 1:

Notice that $\ln(n)<n^k$ for any positive $k$ when $n$ is large enough. Now $\log4_3=\ln(4)/\ln(3)\approx 1.26$ so as long as $r<\ln4/\ln3 -1\approx 0.26$ the analysis is correct.

Edit 1:

A rule of thumb in such analysis is that "logarithmic functions grow much slower than polynomials and they in turn grow much slower than exponential functions". An example of this general idea is $\ln n < n^k$ for positive $k$ and for large $n$. Or as they write it with big O notation $\ln n = O(n^k)$.

Remember what big O means, we say $f(x)=O(g(x))$ as $x\to\infty$ if there is a positive constant $M$ and some threshold $x_0$ such that $|f(x)|<M|g(x)|$ for $x>x_0$. That means $f$ does not grow faster than $g$ when we go to large $x$s.

One of the main tools in proving big O problems is L'Hospital Rule. You can find it in your calculus book. We can actually show very easily that $\lim_{n\to\infty} {\ln n /n^k}=0$. So in fact for $any$ positive M $\ln(n)$ is eventually smaller than $n^k$.

Here how you apply L'Hospital Rule: $\lim_{n\to\infty} {\ln n /n^k}=\lim_{n\to\infty} {(\ln n)' \over (n^k)'}=\lim {{1/n}\over{kn^{k-1}}} =\lim {1/kn^k}=0$. Which true for any $k>0$.