Analysis of Algorithms
In solving any problems, provide as many detailed steps as necessary. If steps are needed to reach the final result,
and you present only the result, the grade for the question will be negatively affected even if the answer is correct.
Problem 1: (25 pts) Find the order of growth for solutions of the following recurrences:
1. T(n) = 2T(n/2) + n, T(1) = 1
2. T(n) = 3T(n/3) + n2, T(1) = 1
3. T(n) = 4T(n/2) + n, T(1) = 1