Question & Answer: Hi, can you use the iterative substitution method to derive the runtime of the following recurrence?…..

T(n) = 4T(n/2) + n2
     = n2 + 4[4T(n/4) + n²/4]
     = 2n2 + 16T(n/4)  
     = k⋅n2 + 4kT(n/2k) 
     = ...

up series will end when 2^k = n.
k = log₂n —taking logarthmic

after substitution k.n² becomes n²logn , 4^kT(n/2^k) this will evaluate to n² as n²logn  asymptotically greater than n² so answer evaluates to

T(n) = O(n²logn)