Please show complete correct neat solution for goodfeedback

Please show complete correct neat solution for goodfeedback and full points thanks

(a) 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, T E 11 ny satisfy l ST 1 if T then 2 L return A 3 else if T l 1 then 4 L return max(Ale, ALT 5 else mid 7 return max (FindMax l, mid) ,FindMax(mid 1, T)) 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

Solution

For algorithm 1, step-7 will split the algo. in two equal parts while other steps take constant amount of time. So, recurrence relation will be

T(n) = 2(Tn/2) + c .

For algorithm 2, there are computation of 7 matrices of size n/2 x n/2 calls to (step-7 to step-13) which divides the problem into halves and addition and subtraction (18 in total - 10 while computing P1 to P7 and 8 while computing C11 to C22) will take order of (n/2)^2. So, overall recurrence will be

T(n) = 7T(n/2) + 18 *(n/2)^2 = 7T(n/2) + 4.5 n^2 Hope it helps,do give your response.