Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I am of the view that this can be solved via master theorem somehow –  csnoob Jan 16 '13 at 14:27

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
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. –  csnoob Jan 16 '13 at 14:26
    
Perhaps this is not a problem for a beginner? –  GEdgar Jan 16 '13 at 14:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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