World's most popular travel blog for travel bloggers.

Runtime of this function: $T(n) = 8T(n/3)+nlogn$

, ,
Problem Detail:

I need to find the runtime of this function: $$T(n) = 8T(n/3)+nlogn$$

I try to use the "Master Theorem" when $$a=8,b=3$$ $$n^{log_ba}=n^{log_38}$$ $$f(n)=nlogn$$ And I define: $$\varepsilon = -1.5+log_3 8$$ the first option in "Master Theorem" its that (when $\varepsilon >0$): $$f(n)=nlogn=O(n^{log_3 8-\varepsilon})$$ So: $$f(n)=nlogn=O(n^{log_3 8-(-1.5+log_3 8)})$$ $$f(n)=nlogn=O(n^{1.5})$$

And its ture! So I can say that the runtime its: $$T(n)=\Theta (n^{log_3 8})$$

That`s true? and why I can say that $\varepsilon=-1.5+log_3 8>0$ I dont have calculator in the exam!

Thank you for help :)

You only need to make sure that $\log_{3}8 > 1$ which is easy to see.

Let $\log_3{8} = 1 + \delta$, $\delta > 0$. Set $0 < \epsilon < \delta$. We have $n^{\log_3{8} - \epsilon} > n^1$.

So $n \log n = O(n^{\log_{3}8 - \epsilon})$.