[Solved]: Recurrence Problem $T(n) = 3T(n/3) + n$

Problem Detail: 

My question here is dealing with the residual that I get. We are trying to prove $T(n) = 3T(n/3) + n$ is $O(n*\log n)$. So where I get is $T(n) \le cn[\log n - \log 3] + n$. So my residual is $-cn\log 3 + n$. So if I minus it I get $-(cn\log 3 -n) \ge 0$ right? How do I figure out what values of c & n are? Do I use the base case? And as long as my negative residual is greater than 0 then my desire is correct because as n grows large then the residual doesn't matter?

Asked By : pmac89

Answered By : nitishch

You are trying to prove $T(n)\le c\cdot n\log n$. Substituting in the equation, you get the recursive structure as $T(n)\le c\cdot n\log n-\left(c\cdot n\log 3-n\right)$. Since $\log 3 >0,$ even for $c=1$, the residual will be greater than $0$. This is exactly what you wanted. You don't need to take any base case because if the equation $T(n)\le c\cdot n\log n$ is true for $c=1$, it is also true for $c>1$.

Finally, your residual is correct.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21952