Write a recurrence describing the number of times the algorithm compares two members of array A,...

  

Transcribed Image Text:

Write a recurrence describing the number of times the algorithm compares two members of array A, measured as a function of the array length n. You do not need to solve the recurrence relation exactly, but state if the solution is linear growth, polynomial growth or exponential growth. Activate Go to Setting foo (int A[], int start, int end) { //initial call foo (array, 0, array.length) if (end A[end-1]) { } swap A[start] and A[end-1] foo (A, start+1, end-2); if (A[start] > A[start+1]) { } swap A[start] and A[start+1] foo (A, start+1, end-1); } Write a recurrence describing the number of times the algorithm compares two members of array A, measured as a function of the array length n. You do not need to solve the recurrence relation exactly, but state if the solution is linear growth, polynomial growth or exponential growth. Activate Go to Setting foo (int A[], int start, int end) { //initial call foo (array, 0, array.length) if (end A[end-1]) { } swap A[start] and A[end-1] foo (A, start+1, end-2); if (A[start] > A[start+1]) { } swap A[start] and A[start+1] foo (A, start+1, end-1); }