13. Consider the following recursive function: int F(int A[], int left, int right) { if (left...

   

Transcribed Image Text:

13. Consider the following recursive function: int F(int A[], int left, int right) { if (left right) return A [left]; int middle left (right-left)/2; int x = F(A, left, middle); int y F(A, middle+1, right); if (xy) return x; else return y; } //end-F a. Draw the recursion tree that results from the call F(A=[3, 5, 2, 4, 8, 9, 3, 4], 0, 7), and explain what this function computes as its output in general. b. Write the recurrence that expresses the running time of this function. c. Express the running time in big-O notation by solving the recurrence using repeated expansions. 14. In order to find the largest element of a given array A[0..n-1] of size n, consider the following recursive algorithm: We first find the largest element of A[1..n-1] and compare the result with A[0] to find the overall largest element. a. Write the pseudo-code for this algorithm b. Express the running time as a recurrence and solve the recurrence by any method you like c. Express the running time in terms of big-O notation 15. In order to find the largest element of a given array A[0..n-1] of size n, consider the following recursive algorithm: We divide the array into 2 subarrays each of size n/2, find the largest of each subarray in a recursive manner, then find the overall largest by comparing the two largest elements. a. Write the pseudo-code for this algorithm b. Express the running time as a recurrence and solve the recurrence by any method you like c. Express the running time in terms of big-O notation 13. Consider the following recursive function: int F(int A[], int left, int right) { if (left right) return A [left]; int middle left (right-left)/2; int x = F(A, left, middle); int y F(A, middle+1, right); if (xy) return x; else return y; } //end-F a. Draw the recursion tree that results from the call F(A=[3, 5, 2, 4, 8, 9, 3, 4], 0, 7), and explain what this function computes as its output in general. b. Write the recurrence that expresses the running time of this function. c. Express the running time in big-O notation by solving the recurrence using repeated expansions. 14. In order to find the largest element of a given array A[0..n-1] of size n, consider the following recursive algorithm: We first find the largest element of A[1..n-1] and compare the result with A[0] to find the overall largest element. a. Write the pseudo-code for this algorithm b. Express the running time as a recurrence and solve the recurrence by any method you like c. Express the running time in terms of big-O notation 15. In order to find the largest element of a given array A[0..n-1] of size n, consider the following recursive algorithm: We divide the array into 2 subarrays each of size n/2, find the largest of each subarray in a recursive manner, then find the overall largest by comparing the two largest elements. a. Write the pseudo-code for this algorithm b. Express the running time as a recurrence and solve the recurrence by any method you like c. Express the running time in terms of big-O notation