For each of the following recurrences, give an expression for the runtime T (n) if the recurrence can be solved with the Master Theorem. Otherwise, indicate that the Master Theorem does not apply.

1. T (n) = 3T (n/2) + n 2

2. T (n) = 4T (n/2) + n 2

3. T (n) = T (n/2) + 2n

4. T (n) = 2nT (n/2) + nn