*Using this code for #1-4 below 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); } }

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-Onotation 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.