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

-
In fact $n\log n = O(n^{1+\epsilon})$ for any $\epsilon > 0$. Hint. $f = O(g)$ implies that $\lim \limits_{n \to \infty} \frac{f}{g}$ is finite (if it exists at all). – Karolis Juodelė Jan 7 '13 at 15:56
Is there a specific $r$ you have in mind? Or is the claim that there exists an $r$ such that the result follows? – Shaun Ault Jan 7 '13 at 15:56
Actually it is what the master method (or masther theorem) says. if $f(n) = O(n^{log_b a-r})$, where in this case $a=4$, $b=3$, $f(n) = nlgn$, then $T(n)=\Theta(n^{log_b a})$ – BRabbit27 Jan 7 '13 at 16:04

Actually we can use the summation formula from above to better estimate the second term for the upper bound. The value is $$2\sum_{j=0}^{\lfloor \log_3 n \rfloor} j 4^j \sum_{k=0}^{\lfloor \log_3 n \rfloor - j } 3^k = \sum_{j=0}^{\lfloor \log_3 n \rfloor} j 4^j (3^{1+\lfloor \log_3 n \rfloor - j}-1) = 3^{1+\lfloor \log_3 n \rfloor } \sum_{j=0}^{\lfloor \log_3 n \rfloor} j \left(\frac{4}{3}\right)^j -\sum_{j=0}^{\lfloor \log_3 n \rfloor} j 4^j$$ We have seen the first term, its value is $$3 \lfloor \log_3 n \rfloor 4^{1 + \lfloor \log_3 n \rfloor} - 9 \times 4^{1 + \lfloor \log_3 n \rfloor} + 12 \times 3^{1 + \lfloor \log_3 n \rfloor}.$$ The second term is $$\frac{1}{9} \left( \lfloor \log_3 n \rfloor 4^{2+\lfloor \log_3 n \rfloor} -(1+\lfloor \log_3 n \rfloor) 4^{1+\lfloor \log_3 n \rfloor} +4 \right)$$ or $$\frac{1}{3} \lfloor \log_3 n \rfloor 4^{1+\lfloor \log_3 n \rfloor} - \frac{1}{9} 4^{1+\lfloor \log_3 n \rfloor} + \frac{4}{9}.$$ Collecting terms we obtain $$\frac{8}{3} \lfloor \log_3 n \rfloor 4^{1 + \lfloor \log_3 n \rfloor} - \frac{80}{9} \times 4^{1 + \lfloor \log_3 n \rfloor} + 12 \times 3^{1 + \lfloor \log_3 n \rfloor} - \frac{4}{9}.$$ This gives the improved upper bound $$T(n) \le 3 \lfloor \log_3 n \rfloor \left( 4^{1+\lfloor \log_3 n \rfloor} - 3^{1+\lfloor \log_3 n \rfloor}\right) - \frac{8}{3} \lfloor \log_3 n \rfloor 4^{1 + \lfloor \log_3 n \rfloor} + \frac{80}{9} \times 4^{1 + \lfloor \log_3 n \rfloor} - 12 \times 3^{1 + \lfloor \log_3 n \rfloor} + \frac{4}{9} = \left(\frac{1}{3} \lfloor \log_3 n \rfloor + \frac{80}{9} \right) 4^{1 + \lfloor \log_3 n \rfloor} - \left( 3 \lfloor \log_3 n \rfloor + 12 \right) 3^{1 + \lfloor \log_3 n \rfloor} + \frac{4}{9}.$$ The term $$\sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j = \frac{1}{3} 4^{1+\lfloor \log_3 n \rfloor} - \frac{1}{3}$$ was dropped from the previous post. We now include it to obtain $$T(n) \le \frac{80}{9} 4^{1 + \lfloor \log_3 n \rfloor} - \left( 3 \lfloor \log_3 n \rfloor + 12 \right) 3^{1 + \lfloor \log_3 n \rfloor} + \frac{1}{3} \lfloor \log_3 n \rfloor + \frac{4}{9}.$$ Taking the two bounds together, we have shown that $$T(n) \in \Theta\left(4^{\lfloor \log_3 n \rfloor} \right) = \Theta\left(n^{\log_3 4}\right).$$ The growth from the recursive term is asymptotically dominant compared to the cost at the recursive step. If there are any doubts as to whether the modified recurrence represents the original problem correctly, recall that changing the base of a logarithm only produces a scale factor, which remains constant during the entire recursion.

-

This problem may be treated the same way as seen in this message here, where we saw that there is an explicit formula for $T(n).$ Let $$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 3^k$$ be the representation of $n$ in base three. Let $T(0)=0$ as before and change the recurrence slightly, in a way that does not affect the asymptotics: $$T(n) = 4 T(n/3) + n \lfloor \log_3 n \rfloor.$$ Then we have by inspection that $$T(n) = \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j \left( \lfloor \log_3 n \rfloor - j \right) \sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^{k-j} = \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j \left( \lfloor \log_3 n \rfloor - j \right) \sum_{k=0}^{\lfloor \log_3 n \rfloor - j } d_{k+j} 3^k = \lfloor \log_3 n \rfloor \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j \sum_{k=0}^{\lfloor \log_3 n \rfloor - j } d_{k+j} 3^k - \sum_{j=0}^{\lfloor \log_3 n \rfloor} j 4^j \sum_{k=0}^{\lfloor \log_3 n \rfloor - j } d_{k+j} 3^k .$$ Now recall the upper bound for the first term that was established in the above cited post which gives the following result in the present context: $$T(n) \le 3 \lfloor \log_3 n \rfloor \left( 4^{1+\lfloor \log_3 n \rfloor} - 3^{1+\lfloor \log_3 n \rfloor}\right) .$$ For a lower bound take the lower bound from the cited post for the first term ($n$ is a one followed by zeros), which gives for the second term $$\sum_{j=0}^{\lfloor \log_3 n \rfloor} j 4^j 3^{\lfloor \log_3 n \rfloor-j} = 3^{\lfloor \log_3 n \rfloor} \sum_{j=0}^{\lfloor \log_3 n \rfloor} j \left(\frac{4}{3}\right)^j$$ Now observe that $$\sum_{j=0}^q z^j = \frac{z^{q+1}-1}{z-1}$$ implies $$\sum_{j=0}^q j z^j = z \frac{d}{dz} \frac{z^{q+1}-1}{z-1} = \frac{1}{(z-1)^2} \left( q z^{q+2} - (q+1) z^{q+1} +z\right)$$ giving $$3^{\lfloor \log_3 n \rfloor} \times 9 \times \left( \lfloor \log_3 n \rfloor \left(\frac{4}{3}\right)^{2 + \lfloor \log_3 n \rfloor} - (1+ \lfloor \log_3 n \rfloor) \left(\frac{4}{3}\right)^{1 + \lfloor \log_3 n \rfloor} + \frac{4}{3} \right)$$ which is equal to $$\lfloor \log_3 n \rfloor 4^{2 + \lfloor \log_3 n \rfloor} - 3 (1+ \lfloor \log_3 n \rfloor) 4^{1 + \lfloor \log_3 n \rfloor} + 4 \times 3^{1 + \lfloor \log_3 n \rfloor}$$ which becomes in turn $$\lfloor \log_3 n \rfloor 4^{1 + \lfloor \log_3 n \rfloor} - 3 \times 4^{1 + \lfloor \log_3 n \rfloor} + 4 \times 3^{1 + \lfloor \log_3 n \rfloor}$$ finally giving a lower bound of $$4 \lfloor \log_3 n \rfloor 4^{\lfloor \log_3 n \rfloor} - 3\lfloor \log_3 n \rfloor 3^{\lfloor \log_3 n \rfloor} - \lfloor \log_3 n \rfloor 4^{1 + \lfloor \log_3 n \rfloor} + 3 \times 4^{1 + \lfloor \log_3 n \rfloor} - 4 \times 3^{1 + \lfloor \log_3 n \rfloor}.$$ so that $$T(n) \ge 3 \times 4^{1+\lfloor \log_3 n \rfloor} - (\lfloor \log_3 n \rfloor +4) 3^{1+\lfloor \log_3 n \rfloor}.$$

-

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

-
Could you develop a little bit more your answer, please. I don't get where the equation $ln(n) < n^k$ came from, but think your answer is what can help me understand. – BRabbit27 Jan 7 '13 at 16:06
Cannot see that $n lg n = O(n^{log_3 4 - r})$ holds for a suitable choose of $r$ – BRabbit27 Jan 7 '13 at 16:16
Yes I agree with you, but this is comparing those functions $ln(n)$ and $n^k$. What I'm asking for is compare $n*lg(n)$ and $n^k$, i.e., the logarithm is being multiplied by $n$ which I would say grows faster, i.e., $n*lg(n) = \Omega(n^k)$ am I right? – BRabbit27 Jan 7 '13 at 19:56
@BRabbit27 Just divide both sides by $n$. In other words if $lg(n)=O(n^k)$ then $nlg(n)=O(n^{1+k})$ for $k>0$. – Maesumi Jan 7 '13 at 20:41