Part A: Experimental Discovery of Time Complexity You must develop and perform a
ID: 3671800 • Letter: P
Question
Part A: Experimental Discovery of Time Complexity You must develop and perform a repeatable experimental procedure that will allow you to empirically discover the time complexity (in term of big-Oh) of the timeTrial(int N) method in the TimingLab class. The parameter N represents the problem size. Thus, by iteratively calling timeTrial with successively larger values of N, you can collect timing data that is useful for characterizing the method's time complexity The constructor TimingLab(int key) will create a TimingLab object whose timeTrial method is tai- lored specifically to the given key value. You will use your group number in Canvas as the key required by the constructor. For example, group 42 would invoke the constructor TimingLab (42) and group 23 would invoke the constructor TimingLab (23). This will create two distinct objects whose timeTrial methods would (very likely) have different time complexities. You are guaranteed that for any key value used, the associated time complexity will be proportional to N* for some positive integer k. Thus, you can take advantage of the following property of polynomial time complexity functions T(N) COMP 2210 Spring 2016 This property tells us that as N is successively doubled, the ratio of the method's running time on the current problem size to the method's running time on the previous problem size (i.e., T(2N)/T(N)) converges to a numerical constant, call it R, that is equal to 2*, and thus k log2R. As an example, consider the data shown in Table 1. Each row in this table records data for a given run of some method being timed. The first column (N) records the problem size, the second column (Time) records the time taken for the method to run on this problem size, the third column (R) is the ratio discussed above (i.e., Timei/Time,-1), and the third column (k) is log2 R. From Property 1 and Table 1 we can hypothesize that the method being timed has O(N4) time complexityExplanation / Answer
public class TimingLabClient {
public static void main(String[] args) {
// some useful variables that you will need in
// your own code
double BILLION = 1_000_000_000d; // nanoseconds to seconds
double start = 0; // start time of the current run
double elapsedTime = 0; // elapsed time of current run
double prevTime = 0; // elapsed time of previous run
double ratio = 1; // currentTime / prevTime
double lgratio = 0; // log base 2 of ratio
int N = 8; // problem size parameter
int key = 22; // selects internal method of RunningTime
// time a single method in this class
start = System.nanoTime();
foo();
elapsedTime = (System.nanoTime() - start) / BILLION;
System.out.print("This call to method foo() took ");
System.out.printf("%4.3f", elapsedTime);
System.out.println(" seconds.");
// measure elapsed time for a single call to timeTrial
TimingLab tl = new TimingLab(key);
start = System.nanoTime();
tl.timeTrial(N);
elapsedTime = (System.nanoTime() - start) / BILLION;
System.out.print("This call to method TimingLab.timeTrial("
+ N + ") took ");
System.out.printf("%4.3f", elapsedTime);
System.out.println(" seconds.");
// measure elapsed time for multiple calls to timeTrial
// with increasing N values
System.out.print("Timing multiple calls to timeTrial(N) ");
System.out.println("with increasing N values.");
System.out.println("N Elapsed Time (sec)");
for (int i = 0; i < 5; i++) {
start = System.nanoTime();
tl.timeTrial(N);
elapsedTime = (System.nanoTime() - start) / BILLION;
System.out.print(N + " ");
System.out.printf("%4.3f ", elapsedTime);
N *= 2;
}
}
// Something that will hopefully take time >= 0.001 seconds
// so that the program output looks better.
private static void foo() {
for (int i = 0; i < 100000; i++) {
String s1 = "War";
String s2 = "Eagle";
String s3 = s1 + s2;
s1 = null;
s2 = null;
s3 = null;
}
}
}