B please Procedure MYSTERY int n int a if n 0 then return 0

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.

Solution

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

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