PROBLEM 1

Use Master Method to find solution (T(n) = BigTheta(?)) for the following recurrence equations, if possible. If not possible, indicate why.

a) T(n)=16T(n/4)+n²

b) T(n) = 4T(n/4)+n

c) T(n)=T(n-2) + 2n²

PROBLEM 2

Use the substitution method to show that for the recurrence equation:

T( 1 )=8

T( n )=T(n-1) + 4n

the solution is T( n )=O( n² )