For each of the following programming fragments:

(a) Give an analysis of the running time (big will do).

(b) Implement the code in Java and give the running times for several values of n.

(c) Compare analysis with the running times.

For these problems, it should be clear that the best-, average-, and worst- case times are the same up to experimental noise.

for(int i=0; i

sum++;

long sum = 0;

for(int i=0; i

for(int j=0;j

sum++;

long sum = 0;

for(int i=0; i

for(int j=0;j

sum++;

long sum = 0;

for(int i=0; i

for(int j=0;j

sum++;

long sum = 0;

for(int i=0; i

for(int j=0;j

for(int k=0;k

long sum = 0;

for(int i=0; i

for(int j=0;j

if (j % i == 0)

for(int k=0;k

sum++;

In most of the problems the running time is likely polynomial in n. If T(n) = cnk for some constant c and some integer k > 0. In this case plotting log T(n) versus log n should give a straight line with slope k and y-intercept log c.

Choose maximal nmax-value for each problem so as to get an easily measurable time, preferably a nice round number, then choose equal increments from n = 0 up to n = nmax at which to run measurements.