MHB Master Theorem-Relation of the two functions

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Functions Master
AI Thread Summary
The discussion focuses on solving the recurrence relation T(n) = 4T(n/3) + n log n using the Master Theorem. The parameters are identified as a = 4, b = 3, and f(n) = n log n, with the calculation of log_b(a) = log_3(4). It is established that n^log_3(4) grows faster than n log n, as polynomials dominate logarithmic functions for large n. The proof using L'Hôpital's rule confirms that the logarithm becomes negligible compared to polynomial growth. This understanding aids in applying the Master Theorem to analyze the recurrence relation effectively.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Physics news on Phys.org
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$$
🤔
 
Klaas van Aarsen said:
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)
 

Similar threads

Back
Top