Consider the following recursive function that takes as arguments an array L and

Question

Consider the following recursive function that takes as arguments an array L and non negative integers first and last, that serve as indices into L. Therefore, if L has length n, then first and last are guaranteed to be In the range 0 through n - 1 What is the value returned by the function call strangeSum(L, 0, 3) where L is the array [1, 4, 2, 3]. Write a recurrence relation describing the running time the function call strangeSum(L, D, n-1) on an array L of length n. Solve the recurrence in (b) to obtain the running time of the function call strangeSum(L, 0, n-1), in terms of n, the length of the given array L.

Explanation / Answer

a)

leftSum <- strangeSum(L,0,1) =5

midSum <- strangeSum(L,1,2)=6

rightSum <- strangeSum(L,2,3)=5

totat = leftSum + midSum+ rightSum = 5+6+5 =16

b) T(n) = 3 T(n/2) + O(1)

leftSum is T(n/2)

midSum is T(n/2)

rightSum is T(n/2)

Thus T(n) = 3(Tn/2) + O(1)

c)

Running Time = nlog23 = n1.58

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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