patternMinor
Solve a recurrence using the master theorem
Viewed 0 times
therecurrencemasterusingsolvetheorem
Problem
This is the recursive formula for which I'm trying to find an asymptotic closed form by the master theorem:
$$T(n)=9T(n/27)+(n \cdot \lg(n))^{1/2}$$
I started with $a=9,b=27$ and $f(n)=(n\cdot \lg n)^{1/2}$ for using the master theorem by $n^{\log_b(a)}$, and if so $n^{\log_{27}(9)}=n^{2/3}$ but I don't understand how to play with the $(n\cdot \lg n)^{1/2}$.
I think that the $(n\cdot \lg n)^{1/2}$ is bigger than $n^{2/3}$ but I'm sure I skip here on something.
I think it fits to the third case of the master theorem.
$$T(n)=9T(n/27)+(n \cdot \lg(n))^{1/2}$$
I started with $a=9,b=27$ and $f(n)=(n\cdot \lg n)^{1/2}$ for using the master theorem by $n^{\log_b(a)}$, and if so $n^{\log_{27}(9)}=n^{2/3}$ but I don't understand how to play with the $(n\cdot \lg n)^{1/2}$.
I think that the $(n\cdot \lg n)^{1/2}$ is bigger than $n^{2/3}$ but I'm sure I skip here on something.
I think it fits to the third case of the master theorem.
Solution
$f(n) = (n\cdot \lg n)^{1/2}$ and $n^{\log_b a}=n^{2/3}$, thus
$f(n) = O(n^{\log_b a})$ and even $f(n) = O(n^{\log_b a - \epsilon})$ for $\epsilon < 1/6$.
Why? because
$$\lim_{n\to\infty} \frac{f(n)}{n^{\log_b a - \epsilon}} = \lim_{n\to\infty}\frac{n^{1/2}\lg^{1/2}n}{n^{2/3-\epsilon}} = \lim_{n\to\infty} \frac{\lg^{1/2}n}{n^{1/6-\epsilon}} =0 \quad\text{for }\epsilon< 1/6$$
Thus case 1 of the Master theorem should apply, and $T(n) = \Theta(n^{2/3})$.
$f(n) = O(n^{\log_b a})$ and even $f(n) = O(n^{\log_b a - \epsilon})$ for $\epsilon < 1/6$.
Why? because
$$\lim_{n\to\infty} \frac{f(n)}{n^{\log_b a - \epsilon}} = \lim_{n\to\infty}\frac{n^{1/2}\lg^{1/2}n}{n^{2/3-\epsilon}} = \lim_{n\to\infty} \frac{\lg^{1/2}n}{n^{1/6-\epsilon}} =0 \quad\text{for }\epsilon< 1/6$$
Thus case 1 of the Master theorem should apply, and $T(n) = \Theta(n^{2/3})$.
Context
StackExchange Computer Science Q#1296, answer score: 5
Revisions (0)
No revisions yet.