I have a recurrence: $T(n) = 4 \cdot T\left(\frac{2n}{3}\right) + (n^3 )\cdot \log(n)$

how can this case be solved from master theorem as this is not in the general form of $T(n) = aT(⌈n/b⌉) + O(nd)$

  • $\begingroup$ I am of the view that this can be solved via master theorem somehow $\endgroup$ – csnoob Jan 16 '13 at 14:27

You are correct that this can be solved via the Master Theorem, though probably not by the version you know. This version of the Master Theorem is more general and states, in part, that if you have a recurrence of the form $$ T(n)=aT(n/b)+f(n) $$ with $a\ge 1, b>1$ (which we have, since $a=4\ge1$ and $b=(3/2)>1$) then if there is a constant $\epsilon>0$ for which $$ f(n)=O(n^{\log_b a -\epsilon}) $$ then $T(n) = \Theta(n^{\log_b a})$.

To see that this is the case we're interested in, note that $\log_{3/2}4\approx3.419$ so if we can establish that there is an $\epsilon>0$ such that $$ f(n) = n^3\log n = O(n^{\log_b a -\epsilon}) $$ then it will follow that $T(n) = \Theta(n^{\log_{3/2} 4})$.

I presume you know that $\log n$ grows asymptotically slower than and positive power of $n$, meaning that for any $\alpha >0$ we'll have $\log n=O(n^\alpha)$ so $$ n^3\log n=O(n^{3+\alpha}) $$ For no particular reason, we'll take $\alpha = 0.4$ then we'll have $n^3\log n=O(n^{3.4})$ and so we'll have $$ f(n)=O(n^{3.4}) = O(n^{3.419-.019})=O(n^{\log_{3/2} 4-\epsilon}) $$ for $\epsilon\approx 0.019$. The conditions of this case of the Master Theorem are satisfied, so $$ T(n)=\Theta(n^{\log_{3/2}4}) $$


Try the substitution $n=(\frac{3}{2})^{u}$

  • $\begingroup$ i am a beginner and do not know how to solve by substitution.I just read the master theorem for solving recurrences. Can yo just outline as how to proceed. $\endgroup$ – csnoob Jan 16 '13 at 14:26
  • $\begingroup$ Perhaps this is not a problem for a beginner? $\endgroup$ – GEdgar Jan 16 '13 at 14:40

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.