Please show all steps to solve the problems in detail. 5. The following pseudoco

Question

Please show all steps to solve the problems in detail. 5. The following pseudocode computes the sum of an array of n integers. int sum (int A , int n) T = A[0] for i= 1 to n-1 return T; (a) Write a recursive version of this code. (b) Let f(n) be the number of additions performed by this computation. Write a recurrence equation for f(n). (Note that the number of addition steps should be exactly the same for both the non- recursive and recursive versions. In fact, they both should make exactly the same sequence of addition steps.) (c) Prove by induction that the solution of the recurrence is f(n) n-1 6. The following pseudocode finds the maximum element in an array of size n int MAX (int Al, int n) { M = A101 for i = 1 to n-1 if i] > M) M = A[i] // Update the max return M; (a) Write a recursive version of this program.

Explanation / Answer

Solution:

5 is done as per Chegg guidelines, please repost others.

a)

The recursive version would be

int sum(int A[], int n)

{

if(n==1)

return A[n];

else

return sum+sum(A, n-1)

}

b)

The recurrence relation for the above code is

f(n) = f(n-1) + c, because at every recursive step 1 constant operation is being done

c)

by using Induction

Base case: T(1)= 0, 0 is the processing time or computation time because the value is only being returned at the base case

f(2) = f(1) + 1 = 1

f(3) = f(2) + 1 = 2

.

.

which proves

f(n) = n-1

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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