Can the master method be applied to the recurrence ? Why or why not? Give an asymptotic upper bound for this recurrence.

In the given recurrence, and . Hence, and .

Now, asymptotically is definitely larger than , but it is not polynomically larger than . So, we cannot apply master method to this recurrence.

We can use recursion tree to get a good estimate of the asymptotic upper bound of the given reference and then use substitution method to prove that.

Rate of increase in number of subproblems in each recursion = 4 Rate of decrease in subproblem size = 2

Hence in each level of the tree, there are nodes each of cost at depth .

Hence, total cost of the tree is:

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