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: