Analysis of algorithm procedure MYSTERYint n int a if n 0 t

Analysis of algorithm

procedure MYSTERY(int n, int a) if (n == 0) then return 0 end if int tmpl = 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

(a) The mystery function computes the product of two numbers i.e n * a .It is actually finding sum of a number n times which is equal to product of n and a .

(c) Yes,this mystery function is a divide and conquer algorithm.As the divide and conquer algorithm does it will divide the program into sub programs.Here, also ,it divides the number \'n\' by 2 continously untill it reaches 0 .And then, it adds the constant \'a\' that many times in each sub program through for loop.And,each result of the sub program is added and returned back.Resulting into a final program where the sum of a number constant that too \'n\' times