Problem 1 (2 points) Solving Recurrence Relations Draw the recursion tree for T(n) = 3T (Ln/2)) + cn, where c is a constant, and provide a tight asymptotic bound on its solution. Verify your bound using the substitution method. Problem 2 (2 points) Solving Recurrence Relations Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n using Heapsort; (2) (2 points) We can build a heap by repeatedly calling Max-Heap-Insert to insert the elements into the heap. Consider the following variation on the Build-Max-Heap procedure: Build-Max-Heap (A) 1 A.heap-size = 1 2 for i = 2 to A.length 3 Max-Heap-Insert(A, A[i]) a. Build a max-heap on the array A in (1) using Build-Max-Heap"; b. Show that in the worst case, Build-Max-Heap requires O'n lg n) time to build an n-element heap