B please! Procedure MYSTERY (int n, int a) if (n == 0) then return 0 end if int

Question

B please!

Procedure MYSTERY (int n, int a) if (n == 0) then return 0 end if int tmp1 = MYSTERY (n/2, a)//assume n/2 rounds down. int tmp2 = 0 for int i = 1 to n/2 do tmp2 + = a end for if (n%2 == 1) then return tmp1 + tmp2 + a else return tmp1 + tmp2 end if end procedure Consider the previous recursive algorithm MYSTERY that takes as input integers n and a What does the mystery function compute Set up a runtime recurrence for the mystery method above. Do not forget the base case. Is this mystery function a divide-and-conquer algorithm? Briefly justify your answer.

Explanation / Answer

Let T(n) be runtime of the algorithm when called with (n,a).

T(n) = T(n/2) + O(n)
T(0)=0

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

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