Consider the following mystery method that is passed a non-null array filled wit
ID: 3679336 • Letter: C
Question
Consider the following mystery method that is passed a non-null array filled with integers and that uses a recursive companion method:
Answer the following questions regarding the code above:
a) What is returned by calling mystery(A) if A contains 7, 6, 5, 4?
b) What is returned by calling mystery(A) if A contains 5, 2, 5, 8, 7, 2, 4?
C) 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.
d) 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.
e) Analyze the time complexity for the recursive companion method above:
1) Identify the problem size that affects the method's runtime.
2) Write the recurrence equations for base and recursive cases.
(You may assume the array size is some power of 2.)
3) Determine the solution by looking for a pattern in the table.
4) Verify the solution by substituting it into the recurrence equation.
5) Determine the method's complexity by expressing the solution in big-O notation.
please do parts C and E in as much detail as you can!
Explanation / Answer
for 7654 it will return 22.
for 5, 2, 5, 8, 7, 2, 4 it will return 33.
The code is basically dividing the given array in two parts repeatedly and is then doing the sum of these parts. So overall the sum of the given array will be returned with method mystery.
Mystery method basically sums up the given array.
the problem will be the size of the array. If the array size is big it may result in stack overflow issues.
recurrence relation is simple
T(n) = T(n/2) + T(n/2 + 1)
The solution will take O(logn) time to run effectively
c)
The execution tree will look like
8
10 12
17 24
29 33
e)
The problem that effects the run time is the stack problem as recursion is used here which may create problems of stack overflow.
I have already mentioned above the recurrence relatoin.