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 .