3) The following divide-and-conquer algorithm performs some mysterious function on an array A[s..t]. The initial call...

 

Transcribed Image Text:

3) The following divide-and-conquer algorithm performs some mysterious function on an array A[s..t]. The initial call to this recursive function is Find(1, 0, n-1) for an array of n elements. int t) { boolean Find (dtype A[], int 8, if (st) return true; //n-1 returns with a true value. if (A[s] A[t]) return false; int m= [(s+1)/2]; if (Find(A, s, m) and Find(A, m + 1,1)) return true; else } return false; a) What does this function accomplish? b) The recurrence relation T(n) for this function is as follows: T(n)-2 T(n/2)+1, T(1)=0 Solve this recurrence relation using backward substitution. 3) The following divide-and-conquer algorithm performs some mysterious function on an array A[s..t]. The initial call to this recursive function is Find(1, 0, n-1) for an array of n elements. int t) { boolean Find (dtype A[], int 8, if (st) return true; //n-1 returns with a true value. if (A[s] A[t]) return false; int m= [(s+1)/2]; if (Find(A, s, m) and Find(A, m + 1,1)) return true; else } return false; a) What does this function accomplish? b) The recurrence relation T(n) for this function is as follows: T(n)-2 T(n/2)+1, T(1)=0 Solve this recurrence relation using backward substitution.