Problem 4 (20 points) Find a function () for each part such that () = ( ()). The base case for each

part is (1) = 1. You can either use the Master theorem or any other valid mathematical proof to

justify your answer.

4.1 () = 11 (/5) + ^2

4.2 () = 3 (/3) + 1

4.3 () = 8 (/3) +

4.4 () = () + 1

Problem 4 (20 points) Find a function f(n) for each part such that T(n)=(f(n)). The base case for each part is T(1)=1. You can either use the Master theorem or any other valid mathematical proof to justify your answer. 4.1 T(n)=11T(n/5)+n2 4.2 T(n)=3T(n/3)+1 4.3T(n)=8T(n/3)+n 4.4T(n)=T(n)+1