For each of the following algorithms, write a recurrence relation that best desc

Question

For each of the following algorithms, write a recurrence relation that best describes the running time of the algorithm. You don't need to prove the algorithm is correct or solve the recurrence; just write it down. Algorithm 1: FindMax(A l, r) Input: A is an array of real numbers, indexed from 1 to n; l, r {1, .... n} satisfy l lessthanorequalto r 1 if l = r then 2 | return A[l] 3 else if r - l = 1 then 4 return max(A[l], A[r]) 5 else mid = l+r/2; return max(FindMax(l, mid), FindMax(mid + 1, r)) To write a recurrence analyze the next algorithm, it is helpful to know that one can add and subtract two matrices (of the same dimensions) in time proportional to the number of entries in each of the matrices. Algorithm 2: MatrixMultiply(A, B) Input: A, B are n times n square matrices 1 if n = 1 then 2 return A times B 3 else 4 Partition A into A^11, A^12, A^21, A^22 5 Partition B into B^11, B^12, B^21, B^22//Where each is a quarter of the original matrices (m times m where m = n/2) P leftarrow MatrixMultiply(A^11, B^12 - B^22) P_2 leftarrow MatrixMultiply (A^11 + A^12, B^22) P_3 leftarrow MatrixMultiply(A^21 + A^22, B^22) P_4 leftarrow MatrixMultiply (A^22, B^21 - B^11) P_5 leftarrow MatrixMultiply (A^11 + A^22, B^11 + B^22) P_6 leftarrow MatrixMultiply(A^12 - A^22, B^21 + B^22) P_7 leftarrow MatrixMultiply (A^11 - A^21, B^11 - B^12) C^11 leftarrow P_5 + P_4 - P_2 + P_6 C^12 leftarrow P_1 + P_2 C^21 leftarrow P_3 + P_4 C^22 leftarrow P_1 + P_5 - P_3 - P_7 Combine C^11, C^12, C^21, and C^22 into n times n matrix C return C

Explanation / Answer

a) Finding Maximum

Assume n is number of elements in an array

T(n) = 2 * T(n/2) + 1 when n>2

= 1 when n<=2

T(n) represents finding maximum in an array of n elements

b) Assume n is the length of the square matrix of (n*n)

Then T(n) = 2 * n^2 + 7*((n/2) * (n/2)) + 7 * T(n/2) + 4*((n/2) * (n/2)) + n^2 = 7 * T(n/2)+ 14 * n^2 when n>1

= 1 when n=1

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.