University of Texas at El Paso
Banner
Compuer Science
   
Text/HTML Minimize    

CS 2401 Assignment #8

Date Assigned: Friday, April 11, 2008.

Due Date: Monday, April 21, 2008.

Goals: to get a hands on experience with the rate of growth of functions and to experiment with timing of programs.

Assignment: In this assignment, you will time some methods that have various running times. You will generate plots of the running times using spreadsheets.

Twelve methods are given to you:

public static void m0(long n){
for (int i = 1; i<=n;i=i*2)
m12(n);
}

public static void m1(long n){
for (int i = 1; i<=n;i++)
m12(n);
}

public static void m2(long n){
for (int i = 1; i<=n;i++)
m0(n);
}

public static void m3(long n){
for (int i = 1; i<=n;i++)
m1(n);
}

public static void m4(long n){
for (int i = 1; i<=n;i++)
m1(i);
}

public static void m5(long n){
for (int i = 1; i<=n;i++)
m3(i);
}

public static void m6(long n){
if (n>0)
m6(n/2);
}

public static void m7(long n){
if (n>0){
m7(n/2);
m7(n/2);
}
}


public static void m8(long n){
if (n>0){
m1(n);
m8(n/2);
m8(n/2);
}
}

public static void m9(long n){
if (n>0)
m9(n-1);
}

public static void m10(long n){
if (n>0){
m10(n-1);
m10(n-1);
}
}

public static void m11(long n){
if (n>0){
m1(n);
m11(n/2);
}
}

public static void m12(long n){
for(int i =1;i<=100000;i++)
{}
}
You have to time these methods for different values of the parameter n. To do this, use method
System.nanoTime()
to get the current value of the most precise available system timer, in nanoseconds. Call the timer before and after calling the timed method and calculate the time as the difference between the two values. Write the result in an output file. You can write the results as n followed by T(n), the time measured for the call of the timed method. Write a pair of numbers per line, separated by one or more blanks. Then, open your file in a spreadsheet like Excel. To do this, drag your text file into the Excel program. Then, use the insert chart feature (use XY(Scatter)) to include a plot of the time versus n.

Deliverables: Submit a folder containing your program(s) and the spreadsheets you generated.