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 :)

  • $\begingroup$ 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. $\endgroup$ – 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})$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.