2 Design a divide-and-conquer algorithm for finding the maximum element MAX in an unsorted array. Write the running time of the algorithm using a recurrence relation and solve the recurrence 3(a). Solve the following recurrences asymptotically (Do not use Master theorem) G Tn) 8(/2)+n nl- (b) What is the averdge time to perform a successful sequential search for a given element on a randomly permuted array of size n? Prove asymptotic tight bound (0) for the following functions (a) T(n) 15n3 n2+4 (b) T(n) = 2n3 + 4n + 4 4. Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 recursively sort A[I.1] and then insert A[n] into the sorted array A[.n-1]. Derive a recurrence for the running time of this recursive version of insertion sort and give a tight asymptotic (0 notation) bound on the running time. 5. n], we [L-n-1 n: 2 5 2 Design a divide-and-conquer algorithm for finding the maximum element MAX in an unsorted array. Write the running time of the algorithm using a recurrence relation and solve the recurrence 3(a). Solve the following recurrences asymptotically (Do not use Master theorem) G Tn) 8(/2)+n nl- (b) What is the averdge time to perform a successful sequential search for a given element on a randomly permuted array of size n? Prove asymptotic tight bound (0) for the following functions (a) T(n) 15n3 n2+4 (b) T(n) = 2n3 + 4n + 4 4. Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 recursively sort A[I.1] and then insert A[n] into the sorted array A[.n-1]. Derive a recurrence for the running time of this recursive version of insertion sort and give a tight asymptotic (0 notation) bound on the running time. 5. n], we [L-n-1 n: 2 5