Give asymptotic tight upper bounds for the following

Question

Algorithm Assignment

1. Give asymptotic tight upper bounds for the following problems using the Master method to solve and justify your answers. Don't forget to do the additional test for Case 3 where needed. For credit, show your work!

a. T(N) = 3 T(N/2) + N³
b. T(N) = 2 T(N/4) + N²
c. T(N) = 2 T(N/4) + N1/²
d. T(N) = 7 T(N/3) + N²

2. Solve the following using the recurrence tree method to solve and justify your answers.

For credit, show your work!

a. T(N) = 3 T(N/2) + N²
b. T(N) = T(N^1/2) + 1

(HINT: can you rewrite the square root function the way we did with the logarithmic function? This analysis takes two such rewrites, but it works!