I am trying to solve a recurrence using substitution method. The recurrence relation is:
T(n) = 4T(n/2)+n2
My guess is T(n) is Θ(nlogn) (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)<=cn2logn, but that did not work.
I got T(n)<=cn2logn+n2. Then I tried to show that, if T(n)<=c1n2logn-c2n2, then it is also O(n2logn), but that also didn't work and I got T(n)<=c1n2log(n/2)-c2n2+n2`.
How can I solve this recurrence?
T(n) = 4T(n/2) + n2 = n2 + 4[4T(n/4) + n²/4] = 2n2 + 16T(n/4) = ... = k⋅n2 + 4kT(n/2k) = ...
The process stops when 2k
reaches n
.
⇒ k = log2n
⇒ T(n) = O(n2logn)