Kenneth Rosen Edition 7 Exercise 8.2 Question 53 (Page No. 527)

Question

Solve the recurrence relation $T (n) = nT^{2}(n/2)$ with initial condition $T (1) = 6$ when $n = 2^{k}$ for some integer $k.$ [Hint: Let $n = 2^{k}$ and then make the substitution $a_{k} = \log T (2^{k})$ to obtain a linear nonhomogeneous recurrence relation.]

Comments

T(n)=nT2(n/2),T(1)=6,n=2k (log base is 2)

T(2k)=2kT2(2k−1),T(1)=6, Let ak=T(2k),bk=log ak

ak=2k(ak−1)2,a0=6

     bk=2bk−1+k,b0=log 6bk=(3+log 3)2k−k−2

T(n)=2^(3n−2) 3^n/n