3. Consider the following divide-and-conquer algorithm that takes as input an array A = {0, ,an),...

Transcribed Image Text:

3. Consider the following divide-and-conquer algorithm that takes as input an array A = {0₁, ,an), and two indices I and r such that 1</<r<n. 02--- Algorithm Mystery2(A, 1, r) if r then return a₁ else m+ ← [(1+r)/2] x y Mystery2(A, I, m) Mystery2(A, m+1, r) if x> y return x else return y (c) Analyze the running time T(n) of this algorithm, for 1= 1 and r=n. Set up a recurrence relation and solve it by Master theorem. 3. Consider the following divide-and-conquer algorithm that takes as input an array A = {0₁, ,an), and two indices I and r such that 1</<r<n. 02--- Algorithm Mystery2(A, 1, r) if r then return a₁ else m+ ← [(1+r)/2] x y Mystery2(A, I, m) Mystery2(A, m+1, r) if x> y return x else return y (c) Analyze the running time T(n) of this algorithm, for 1= 1 and r=n. Set up a recurrence relation and solve it by Master theorem.

Answer rating: 100% (QA)

To analyze the running time Tn of Algorithm Mystery2 for l 1 and r n we can set up a recurrence rela... View the full answer