algorithms

3. (20 points) Recurrences (Master Method). Solve each recurrence below using the Master Method and write your final answer using -notation. Make sure that you show all your work including the corresponding case and the values of or k used. If it is not possible to solve a recurrence using the Master Method, prove it by showing that the form is inapplicable or by showing that all 3 cases cannot be satisfied. (a) T(n)=64T(n/8)+3n (b) T(n)=8T(n/2)+n3 (c) T(n)=T(2n)+n2 (d) T(n)=T(3n/10)+n (e) T(n)=2T(n/2)+n (f) T(n)=T(n/7)+lg3n (g) Bonus (+5 points): T(n)=9T(n/3)+sinn