Cormen 4.3.8

Question

Find the solution of recurrence $T(n) = 4T(\frac{n}{2}) + n^{2}$ by substitution method.

Comments

in substitution method, we've to guess solution, so better to do the other methods to avoids error & time in exam hall

---

Subarna Das yeah i prefer the same but just for the sake of learning :p

---

ankitgupta.1729 not given, we are assuming T(1) = 1 

Answer 1

T(n)=4T($\frac{n}{2}$) + n²

        =4{4 * T($\frac{n} {2^2}$) + ($\frac{n}{2}$)²}+ n²

         =4² * T($\frac{n} {2^2}$) + n² + n²

         =4²{4 * T($\frac{n} {2^3}$) + ($\frac{n}{2^2}$)²}+ n² +n²

         =4³ * T($\frac{n} {2^3}$) + n² + n² + n²

         =4^k * T($\frac{n} {2^k}$) + k * n²

so,$\frac{n} {2^k}$ = 1

    => k= $\log_{2}n$

now T(n)=4^k * T($\frac{n} {2^k}$) + k * n²

                =4^$\log_{2}n$  *  T(1) + $\log_{2}n$ * n²

                =2^{$\log_{2}n^2$} + $\log_{2}n$ * n²

                =n² + $\log_{2}n$  * n²

                =O(n² $\log_{2}n$ )

Comments

Isn't this backtracking method?

---

it is Substitution method.