Exercise 4.5-1

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

1. \(T(n) = 2T(n/4) + 1\).
2. \(T(n) = 2T(n/4) + \sqrt n\).
3. \(T(n) = 2T(n/4) + n\).
4. \(T(n) = 2T(n/4) + n^2\).

In all of the recurrences, \(a = 2\) and \(b = 4\).

Hence, \(n^{\log_b a} = n^{1/2} = \sqrt n\).

Recurrence 1

As \(f(n) = O(1) = O(n^{1/2 - 1/2})\), case 1 of master method is applicable.

Hence, \(T(n) = \Theta(\sqrt n)\)

Recurrence 2

As \(f(n) = O(n^{1/2})\), case 2 of master method is applicable.

Hence, \(T(n) = \Theta(\sqrt n \lg n)\)

Recurrence 3

As \(f(n) = O(n) = O(n^{1/2 + 1/2})\), and \(2f(n/4) = n/2 \leq cn\) for \(1/2 \leq c < 1\) and sufficiently large \(n\), case 3 of master is applicable.

Hence, \(T(n) = \Theta(n)\)

Recurrence 4

As \(f(n) = O(n^2) = O(n^{1/2 + 3/2})\), and \(2f(n/4) = n^2/8 \leq cn^2\) for \(1/8 \leq c < 1\) and sufficiently large \(n\), case 3 of master is applicable.

Hence, \(T(n) = \Theta(n^2)\)