Question & Answer: Solve the recurrence relation : T(n) = T(n/2) + n 3 . T(1)=1……

This reccurance relation can be solved using master’s theorem

here in this equation T(n)=T(n/2)+ n³

here a=1 b=2 f(n)= n³

according to master’s theorem if f(n)=Θ(n^c) where c>Log_ba then T(n)=Θ(f(n))

here c=3 and log_ba=log₂1 = 0 so c>0 sot T(n)= Θ(n³).