patternMinor
Solving $T(n)=4T(n/2)+n^2$
Viewed 0 times
solvingstackoverflowprogramming
Problem
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.
$$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.
Solution
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).
$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).
Context
StackExchange Computer Science Q#10227, answer score: 6
Revisions (0)
No revisions yet.