Algorithm Analysis Lab in Java

Attached Files:

AlgorithmAnalysis.java (860 B)

import java.util.Calendar;

public class AlgorithmAnalysis{

public static void main(String[] args){ // pass the value of n as a command line argument long n = Long.parseLong(args[0]);

// counter for output int fragNum = 1; // get current time long startTime = System.nanoTime(); // Fragment 1 long sum = 0; for( int i = 0; i

} // get stop time and calculate actual run time long endTime = System.nanoTime(); long diff = endTime - startTime; System.out.println("Time to compute Fragment " + fragNum++ + " was " + diff + " nanoseconds."); // continue in the same way for the remaining code fragments

}

}

Big-O versus Actual Running Time

For each of the following code fragments, do the following:

(a) Give a Big-O analysis of the running time based on static analysis of the code fragment

(b) Implement the code and run with several values of n.

(c) Compare your analysis with the actual running time by completing the table.

// Fragment 1

for (int i = 0; i

sum++;

// Fragment 2

for (int i = 0; i

sum++;

// Fragment 3

for (int i = 0; i

for (int j = 0; j

sum++;

// Fragment 4

for (int i = 0; i

sum++;

for (int j = 0; j

sum++;

// Fragment 5

for (int i = 0; i

for (int j = 0; j

sum++;

// Fragment 6

for (int i = 0; i

for (int j = 0; j

sum++;

// Fragment 7

for (int i = 0; i

for (int j = 0; j

for (int k = 0; k

sum++;

// Fragment 8

for (int i = 1; i

sum++;

To find the running time, the following code can be used:

long start = System.nanoTime();

//The code being timed goes here

long end = System.nanoTime();

long diff = end - start;

System.out.println(Time to compute Fragment + fragNum + was + diff + milliseconds.);