Please solve (iii) using SUBSTITUTION method and verify.

9. Solve the following RRs with recursion tree. Base case is assumed to be T(1)=1 for all RRs. () T(n)= 4T(n/2)+ n^2. (ii) T(n)= 2T(n/2)+ 2n. (ii) T(n)= 2T(n/2)+ 2n. With the help of substitution method check whether T(n) is (n log n)