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?
$\begingroup$
$\endgroup$
-
2$\begingroup$ Is your question answered here? cs.stackexchange.com/questions/2789/… $\endgroup$ – David Richerby Feb 23 '14 at 19:46
-
$\begingroup$ No. I'm just trying to see if I'm looking at the residual correctly. $\endgroup$ – pmac89 Feb 23 '14 at 22:15
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
Please remember the definition of O(n*logn), if there's a c's value exist, the proposition is right.
In your case, you can assign the c with the value with is less than 1/(log3), and your answer is right.
Anyway, I think this kind of method to solve complexity-theory problem is not quite easy, you may try other methods, such as "recursion tree" or master theorem.
-
1$\begingroup$ It was an example to solve by substitution. And how did you find c? $\endgroup$ – pmac89 Feb 24 '14 at 3:11
