Need help with 3 and 5

3. (20 points) Assume that T(1) (1) and T(n) = T(3n/4) + T(n/2) + n2. Prove T(n) (n2) using the substitution method.

5. (30 points) Analysis of recursive algorithm. Consider the pseudocode of the following two algorithms. The input A is an array of size n. In Algl, A is divided into two subarrays, and the algorithm is recursively applied to only one subarray. In Alg2, A is divided into five subarrays, and the algorithm is recursively applied to two or three of them, depending on values in A. Assume that parameter passing takes constant iine Algl (AL1..n]) Alg2 (A[1..n]) if (n