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 it`s 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 it`s:$$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 :)
Runtime of this function: $T(n) = 8T(n/3)+nlogn$
runtime analysis
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})$.