5
$\begingroup$

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T(n/2)+n^2$$ My guess is $T(n)$ is $\Theta(n\log n)$ (and I am sure about it because of master theorem), and to find an upper bound, I use induction. I tried to show that $T(n)\le cn^2\log n$ but that did not work, I got $T(n)\le cn^2\log n+n^2$.

I then tried to show that, if $T(n)\le c_1 n^2\log n-c_2 n^2$, then it is also $\mathcal O(n^2\log n)$, but that also did not work and I got $T(n)\le c_1n^2\log(n/2)-c_2 n^2+n^2$.

What trick can I use to show that? Thanks.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ the solution should be O(n^2logn). $\endgroup$ – sukunrt Mar 3 '13 at 13:46
  • $\begingroup$ Please have a look at our reference questions, especially under the section "Asymptotics". $\endgroup$ – Paresh Mar 3 '13 at 15:34
  • 2
    $\begingroup$ Also, did you mean $\Theta(n^2\log n)$ instead? Since you are trying to show $T(n) \le cn^2\log n$ later. $\endgroup$ – Paresh Mar 3 '13 at 15:36
  • 1
    $\begingroup$ See Solving or approximating recurrence relations for sequences of numbers, as hinted by @Paresh. $\endgroup$ – Juho Mar 3 '13 at 15:38
  • $\begingroup$ It seems I forgot to link the collection of reference pages. Thanks @Juho $\endgroup$ – Paresh Mar 3 '13 at 15:40
6
$\begingroup$

You must subtract a lower order term in order to strengthen your inductive hypothesis: try

$T(n) \leq c_1 n^2 \lg n- c_2 n$ and you will be able to show by substitution that $T(n) = O(n^2 \lg n)$ for appropriate values of the constants ($c_2 > 1$ and $c_1$ big enough to correctly handle the initial conditions).

Improve this answer
$\endgroup$
3
$\begingroup$

I always use following approach: Try to avoid master theorem as a recursion solution gives you more insight to the structure of the problem:

Recursion

Improve this answer
$\endgroup$
1
$\begingroup$

That's a recurrence of the form: $T(n)=aT(n/b)+f(n)$. In your case $a=4$, $b=2$, and $f(n)=n^2$. This is case 2 of the master theorem. It follows that $T(n)=\Theta(n^2\log n)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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