2. In this exercise you will again experimentally determine the cost of several algorithms in terms of their input size. Note than in all the cases below, the cost is measured by counting the number of times we execute the body of the innermost loop and this is simply the value of the variable: sum.

Create a Java program for each algorithm and run the program for the input values shown, completing a table as shown below. Then plot the data using graphing software. The deliverable is:

the completed table

graph

The answer to the question (see page 1).

N

sum

1000

2000

4000

8000

16000

Algorithms to evaluate:

A)

N = StdIn.readInt();

int sum = 0;

for (int i =1; i

for (int j = 1; j

sum++;

StdOut.println(sum);

B)

N = StdIn.readInt();

int sum = 0;

for (int i =1; i

for (int j = 1; j

sum++;

StdOut.println(sum);

C)

N = StdIn.readInt();

int sum = 0;

for (int i = N; i > 0; i = i/2 )

for (int j = 1; j

sum++;

StdOut.println(sum);

2. In this exercise you will again experimentally determine the cost of several algorithms in terms of their input "size". Note than in all the cases below, the cost is measured by counting the number of times we execute the body of the innermost loop and this is simply the value of the variable: sum. Create a Java program for each algorithm and run the program for the input values shown, completing a table as shown below. Then plot the data using graphing software. The deliverable is: the completed table graph The answer to the question (see page 1). 1000 2000 4000 8000 10000 Algorithms to evaluate: A) N = StdIn.readInt(); int sum = 0; for (int i =1; i 0; i = i/2) for (int j = 1; j 0; i = i/2) for (int j = 1; j