Answer

1. Solve the following recurrence using the "backward substitution" method. T(n)=T(n1)+n3forn>1T(1)=5 Show your work similar to the example from the notes. You do not need to prove the correctness using mathematical induction. Just solve T(n) using - notation, as a function of n. 2. Solve the following recurrence using the "change of variable" method. Use the change of variable m=log3n. Show you work similar to the example from the notes. T(n)=9T(3n)+4(log3n)2