Using the master method in Section 4.5, you can show that the solution to the recurrence is . Show that a substitution proof with the assumption fails. Then show how to subtract off a lower-order term to make a substitution proof work.

Let us assume for all , where and are positive constants.

With this we cannot prove our assumption in it’s exact form.

Now, let us assume for all , where and are positive constants.

Uh oh! From this we cannot say the last step will be less than or equal to when is sufficiently large.

So, what does that mean? This means we are trying to prove a wrong assumption. And if you use Master Theorem, you will see the asymptotic bound of the given recurrence is , not as given in the problem statement.

So, let us assume for all , where and are positive constants.

The last step holds as long as . Hence, our assumption is correct.

PS: As usual we have just proved -bound. But to show -bound, we also need to show -bound, which can be done by adding the lower order term instead of subtracting.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.