-1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It was an example to solve by substitution. And how did you find c? $\endgroup$ – pmac89 Feb 24 '14 at 3:11

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