Problem Set 6
Recurrences 2
1 Master Method Recurrences
For each of the recurrences
1.1
Solution
Apply the master theorem with
To check that the regularity condition holds, we need to check that
Thus, the master theory applies and we have
1.2
Solution
Apply the master theorem with1.3
Solution
Apply the master theorem with
2 Unbalanced Recurrences
2.1
Use any method you want to solve the following recurrence.
By ‘solve the recurrence’, I mean find
Solution
Claim.
Note that
Thus, to show that
We need this expression to be at most