Draw the recursion tree for , where is a constant, and provide a tight assymptotic bound on its solution. Verify your bound by the substitution method.

Ignoring the floors, the recusrion takes the form:

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:

Now, for assymptotic upper bound:

And, for assymptotic upper bound:

Last step holds as long as .

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