Use the master method to give tight asymptotic bounds for the following recurrences.

  1. .
  2. .
  3. .
  4. .

In all of the recurrences, and . Hence, .

Recurrence 1 : Hence,

Recurrence 2 : Hence,

Recurrence 3 : Hence,

Recurrence 4 : Hence,

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