Given an array A[p..r], consider the following recursive algorithm Max. Max(A, p, r) return A[p] 1...

  

Transcribed Image Text:

Given an array A[p..r], consider the following recursive algorithm Max. Max(A, p, r) return A[p] 1 if p == r 2 3 else 4 ST 5 6 7 9 a == = =L(p + + r) / 2 Max (A, p, q) b Max (A, q+1, r) = if a ≥ b 00 8 return a 9 else 10 return b 1. (5pts) Run Max (A, 1, 4) on array A[1..4] = <5, 10, 3, 8>. What will be the output? Show all the recursive calls to Max along with the corresponding return values. 2. (3pts) Write a recurrence relation describing the running time of algorithm Max (A, p, r) in terms of n (= r -p + 1). 3. (4pts) Solve the recurrence relation to give a tight bound (using e) on the running time of algorithm Max. Show the details. You may type "Theta" instead of "e" and type "Omega" instead of ".". Given an array A[p..r], consider the following recursive algorithm Max. Max(A, p, r) return A[p] 1 if p == r 2 3 else 4 ST 5 6 7 9 a == = =L(p + + r) / 2 Max (A, p, q) b Max (A, q+1, r) = if a ≥ b 00 8 return a 9 else 10 return b 1. (5pts) Run Max (A, 1, 4) on array A[1..4] = <5, 10, 3, 8>. What will be the output? Show all the recursive calls to Max along with the corresponding return values. 2. (3pts) Write a recurrence relation describing the running time of algorithm Max (A, p, r) in terms of n (= r -p + 1). 3. (4pts) Solve the recurrence relation to give a tight bound (using e) on the running time of algorithm Max. Show the details. You may type "Theta" instead of "e" and type "Omega" instead of ".".

Answer rating: 100% (QA)

Step 2 Part 2 The recurrence relation describing the running time of algorithm Max A p r in terms of n is Tn 2Tn2 O1 This is because in each recursive ... View the full answer