Given an array A and two indices p and r, consider the following modified merge sort algorithm. Modified-Merge-Sort (A, p, r) 1 if pr 2 nr-p+1 3 4 56 7 8 In/31 Foo (A, P, P+ q) Foo (A, p+q+1, p + 2q) Foo (A, p+2q + 1, r) Merge (A, P, P+q p + 2q) Merge (A, P, p + 2q, r) The Merge procedure is exactly the same one for the Merge-Sort algorithm we discussed in class. 1. (3pts) Write a recurrence relation describing the running time of algorithm Modified-Merge-Sort (A, p, r). Include the base case(s). 2. (2pts) Solve the recurrence relation to give a tight bound on the running time. You don't need to show the details of solving the recurrence. You may type "Theta" instead of "O" and type "Omega" instead of ""