1. (25 Points) The following recursive algorithm determines whether a sub-array A[p --- r] is sorted. The variables B1, B2 and B3 are Boolean, and a represents the Logical And operator. Sorted(A, p, r) precondition: r 2 p 1. if r =p 2. return True 3. else 4. q = [(p+r)/2] 5. B1 = Sorted(A, p, q) 6. B2 = Sorted(A,q + 1,r) 7. B3 = (A[9] = A[q+ 8. return (B11 B2 1 B3) a. (15 Points) Use induction on m = length(A[p ... r]) to prove correctness of the above algorithm, i.e. prove that Sorted(A,p,r) returns True if and only if A[p --- r] is sorted in increasing order b. (10 Points) Let T(n) denote the number of array comparisons performed by Sorted() on an array of length n. Write a recurrence relation for T(n). Determine a tight asymptotic bound for T(n)