Part II: Solving recurrences using the Master Method
For each of the following recurrences, apply the Master Method to find its asymptotic solution. You should use the extended version of the Master Theorem (found on Wikipedia) that we referenced in studio. If this version of the Master Theorem gives no solution, state this. You must show your work for full credit, including:
• the values of a, b, and $f(n)$;
• the test you performed to determine which case of the Master Theorem applies, if any (e.g. $n^2$ vs. $n \log n$), OR the reason why the Master Theorem does not apply, if it does not;
• the result of the test (i.e. which case of the Master Theorem applies, if any);
• the conclusion about asymptotic running time you draw from the result, if any.
3. $T(n) = T(\frac{n}{2}) + \log n$
4. $T(n) = 7T(\frac{n}{3}) + n^2$
5. $T(n) = 26T(\frac{n}{5}) + 12n^2$
6. $T(n) = 4T(\frac{n}{2}) - 4n^2 \log^2 n$
7. $T(n) = 3T(\frac{n}{3}) + \frac{n}{\log n}$
8. $T(n) = 10T(\frac{n}{5}) + 3n^2 \log_{4} 10$
9. $T(n) = 3T(\frac{n}{2}) + n^2 \log \log n$
