Master Theorem-Relation of the two functions

In summary, the conversation is about solving the recurrence relation $T(n)=4T{\left( \frac{n}{3} \right)}+n \log{n}$ using the Master Theorem and discussing the relation between $n^{\log_{3}{4}}$ and $n \log{n}$. It is mentioned that a polynomial dominates the logarithm for sufficiently large values of $n$, and this is proven using L'Hôpital's rule.
  • #1
evinda
Gold Member
MHB
3,836
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
  • #2
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$$
🤔
 
  • #3
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)
 

Related to Master Theorem-Relation of the two functions

1. What is the Master Theorem?

The Master Theorem is a mathematical theorem used to analyze the time complexity of recursive algorithms. It provides a formula for determining the asymptotic behavior of a recurrence relation based on the values of its coefficients.

2. How is the Master Theorem used in computer science?

The Master Theorem is commonly used in computer science to analyze the time complexity of recursive algorithms, which are frequently used in programming. It helps determine the efficiency of these algorithms and can assist in optimizing them.

3. What are the three cases of the Master Theorem?

The three cases of the Master Theorem are: case 1, where the recurrence relation has a polynomial time complexity; case 2, where the recurrence relation has a logarithmic time complexity; and case 3, where the recurrence relation has an exponential time complexity.

4. How do you determine which case of the Master Theorem applies?

To determine which case of the Master Theorem applies, you must compare the values of the coefficients in the recurrence relation to the values in the formula for each case. The case that matches the coefficients in the relation is the one that applies.

5. What is the significance of the Master Theorem in algorithm analysis?

The Master Theorem is significant in algorithm analysis because it provides a quick and easy way to determine the time complexity of recursive algorithms. This allows for more efficient and optimized algorithms to be developed, leading to better performance and faster processing times.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
0
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
13
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
18
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
994
Back
Top