# Solving recurrences $T(n) = 4 T(2n/3) + (n^3 )\cdot \log(n)$

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

-
I am of the view that this can be solved via master theorem somehow –  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}$