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

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 already have a solution to the recurrence and checking people's answers is off-topic, here. The question about whether $\log_3 8 > 1.5$ is purely a mathematical question with no CS content, so that's off-topic, too. – David Richerby May 13 '16 at 14:30

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})$.