PLEASE HELPPPP Assume that we begin with the following initial call to this method: 

foo(5, 3) 

1. Construct a call tree that shows each invocation of the method. In particular, you should:

Begin by copying the following initial diagram into your ps3pr1.txt file:

 1:foo(5,3) / \ / \ / \ 

Add each subsequent call with its parameters to the call tree in the appropriate place.

If a given call is a base case, simply put its return value under the call.

If a given call is not a base case, use lines composed of / or \ characters to connect the call to the recursive call(s) that it makes.

Precede each call with a number that indicates the overall order in which the calls were made.

2. Draw a stack trace of the function execution from the initial call. You can draw the stack in parallel blocks to reflect the changes to the stack when a function returns.

* use this code for #1 & #2 public static int foo(int x, int y) { if (y == 0) { return x; } else if (x <= y) { return y; } else { int result1 = foo(x - 1, y - 1); int result2 = foo(x - 1, y + 1); return result1 + result2; } }

1. Derive an exact formula for the number of times that the line that increases the sum i.e. sum = sum + j is executed, as a function of the parameter n. You may find it helpful to create a table with two columns such that the rst column represents n and the second column shouws the number of times the statement sum = sum + j is executed.

It may be helpful to encode the above code fragment, strategicaly add a counter and exectute the loop with the following values for n:

{1, 5, 10, 15, 20, 25, 30, ..., 140, 145, 150}.

Make sure to populate the second column after running your code against each value of n.

2. What is the time efficiency of the method shown above as a function of the parameter n? Use big-O notation as we did in lecture, and explain your answer briefly.

3. Create an alternative implementation of this method that also uses iteration (i.e., you should not use recursion) but that has a better time efficiency. Test your implementation and copy and paste your Java program into this text file.

4. What is the time efficiency of your alternative implementation as a function of the parameter n? Use big-O notation as we did in lecture, and explain your answer briefly.

*Using this code for #1-4 above public static void generateSums(int n) { for (int i = 1; i <= n; i++) { int sum = 0; for (int j = 1; j <= i; j++) { sum = sum + j; // how many times is this executed? } System.out.println(sum); } }