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 $-cnlog 3 + n$. So if I minus it I get $-(cnlog 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 ccdot nlog n$. Substituting in the equation, you get the recursive structure as $T(n)le ccdot nlog n-left(ccdot nlog 3-nright)$. 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 ccdot nlog 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
