Master Theorem-Relation of the two functions

[evinda]

Hello! (Wave)

I want to solve the recurrence relation

$$T(n)=4T{\left( \frac{n}{3} \right)}+n \log{n}.$$

I thought to use the Master Theorem.

We have $a=4, b=3, f(n)=n \log{n}$.

$\log_b{a}=\log_3{4}$

$n^{\log_b{a}}=n^{\log_3{4}}$

How can we find a relation between $n^{\log_{3}{4}}$ and $n \log{n}$ ? (Thinking)

 

[I like Serena]

Hey evinda!

A polynomial dominates the logarithm doesn't it?
More specifically, for any $\varepsilon>0$ we have that $\ln n < n^\varepsilon$ for sufficiently large $n$.
Proof by L'Hôpital's rule:
$$\lim_{n\to\infty} \frac{\ln n}{n^\varepsilon} = \lim_{n\to\infty} \frac{\frac 1n}{\varepsilon n^{\varepsilon-1}} = \lim_{n\to\infty} \frac{1}{\varepsilon n^\varepsilon} = 0$$

 

[evinda]

Hey evinda!

A polynomial dominates the logarithm doesn't it?
More specifically, for any $\varepsilon>0$ we have that $\ln n < n^\varepsilon$ for sufficiently large $n$.
Proof by L'Hôpital's rule:
$$\lim_{n\to\infty} \frac{\ln n}{n^\varepsilon} = \lim_{n\to\infty} \frac{\frac 1n}{\varepsilon n^{\varepsilon-1}} = \lim_{n\to\infty} \frac{1}{\varepsilon n^\varepsilon} = 0$$

I see... Thanks a lot! (Blush)