Problem t 9 divide-and-conquer (A) Translate this algorithn description into a C

Question

Problem t 9 divide-and-conquer (A) Translate this algorithn description into a C function using the template below NOTE: to get the sun of an array datal] of length n, we call arr sum2 (data, 0, n-1) int arr sun2 (int all.int lo, int hi) (B) For an array of length n, exactly how nany calls/invocations to arr sum20 are made? Give your reasoning- (c) Give a recurrence relation for the runtine of the algorithn. (D) Analyze your recurrence relation and give a big- runtine bound. Show your work/reasoning Appendix: QuickSort implementation void qstint all. int I, int r) int i, j, pivot; ifr-l+1)t if(allaIrD swap(a·l, r); return; I median of three int m - (Hry2 swap(a, l, swapia, r,I); swap (a, r.m swap a, m, r1 pivot- alr-1 i- r-l foran while(al++i] pivot): ifij) break swap(a, i, j swapla, i, r-1); W replace pivot qsta, L, i-1) qsla, i+1, r) void swap(int all, int i, int j) I int tmp tmp- aji alil tmp

Explanation / Answer

Please find my answer.

A)

int arr_sum2(int a[], int lo, int hi) {

// base case

if(lo == hi)

return a[lo];

// recurence

else

return a[lo] + arr_sum2(a, lo+1, hi);

}

B)

sum2() method will be called n times becaue it will kepp increasing until lo equals to hi

C)

Recurence relation:

T(n) = T(n - 1) + O(1)

D)

Solution:

T(n) = T(n - 1) + O(1)

T(n) = T(n - 2) + O(1) + O(1)

--------------

T(n) = T(1) + O(1) + O(1) + .... (n-1) times

T(n) = O(1) + O(1) + O(1) + .... n times

= O(n)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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