Consider the following mystery method that is passed a non-null array filled with integers and that uses a recursive companion method:

public static int mystery(int[] A) { return mystery(A, 0, A.length - 1); } private static int mystery(int[] A, int first, int last) { if (first == last) return A[first]; int middle = (first + last)/2; return mystery(A, first, middle) + mystery(A, middle+1, last); } 

Answer the following questions regarding the code above:

What is returned by calling mystery(A) if A contains 7, 6, 5, 4?

What is returned by calling mystery(A) if A contains 5, 2, 5, 8, 7, 2, 4?

Draw an execution tree trace of the recursive companion method as called in b. above. Draw your tree as shown below listing the values of parameters first and last for each recursive call. Make sure your tree displays correctly in your pdf file.

 0-6 ... + ... ... + ... ... + ... 

What does method mystery(A) do in general? Do not just redescribe the code. Instead, briefly state what the method does at a high level.

Analyze the time complexity for the recursive companion method above:

-Identify the problem size that affects the method's runtime.

-Write the recurrence equations for base and recursive cases. (You may assume the array size is some power of 2.)

-Determine the solution by looking for a pattern in the table.

-Verify the solution by substituting it into the recurrence equation.

-Determine the method's complexity by expressing the solution in big-O notation.