Problem Detail: 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)=(ncdot 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 $(ncdot lg n)^{1/2}$. I think that the $(ncdot 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.
Asked By : Toda Raba
Answered By : Ran G.
$f(n) = (ncdot 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_{ntoinfty} frac{f(n)}{n^{log_b a – epsilon}} = lim_{ntoinfty}frac{n^{1/2}lg^{1/2}n}{n^{2/3-epsilon}} = lim_{ntoinfty} frac{lg^{1/2}n}{n^{1/6-epsilon}} =0 quadtext{for }epsilon< 1/6$$ Thus case 1 of the Master theorem should apply, and $T(n) = Theta(n^{2/3})$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1296
