For example: Run method! 1000 times for n=5000 compute the running time for each
ID: 3690210 • Letter: F
Question
For example: Run method! 1000 times for n=5000 compute the running time for each run, and take the average over 1000 runs. Record this value. a. b. Repeat for different n: [6000, 7000, 8000, 9000, 10000, 11000, 12000, 13000, 14000] c. Then repeat the the same procedure for method2 and methods 4) Using the values from the above experiments create three plots, one for each method. For each plot, the 10 data points will be connected by a smooth curve. The x-axis will be n and the y-axis will be time. You may use any software you wish, but you will be penalized if your graphs are not clear. Screenshot these graphs and include them in plots.pdf. 4) In HW34.txt, write a 3-4 sentences explaining the results of your experiment. Clearly explain the expected (theoretical)running time and the observed running times.Explanation / Answer
Complexity.java
public class Complexity {
/**
* @param args
*/
public static int method1(int num){
int result = 0;
for(int i=num; i>=0; i--){
for(int j=0; j<=i; j++){
result = result + 1;
}
}
return result;
}
public static int method2(int num){
int result = 1;
int i, j=100;
for(i=0; i<=100; i++){
while(j>i){
result = result * num;
j--;
}
j =100;
}
return result;
}
public static void method3(int num){
int[] intArray = new int[num];
for(int i=0; i<num-1; i++)
intArray[i] = i+1;
for(int i=0; i<intArray.length; i++)
System.out.println(intArray[i]);
for(int i=intArray.length - 1; i>0; i--)
intArray[i] = intArray[i-1];
intArray[0] = -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
long startTime = 0;
long lastTime = 0;
System.out.println("--------------Method1-----------------");
for(int num=5000; num<=14000; num = num + 1000 ){
startTime = System.currentTimeMillis();
method1(num);
lastTime = System.currentTimeMillis();
System.out.println("num = "+num+" Took : " + (lastTime - startTime)+" millisecs");
}
System.out.println("--------------Method2-----------------");
for(int num=5000; num<=14000; num = num + 1000 ){
startTime = System.currentTimeMillis();
method2(num);
lastTime = System.currentTimeMillis();
System.out.println("num = "+num+" Took : " + (lastTime - startTime)+" millisecs");
}
System.out.println("--------------Method3-----------------");
String str = "";
for(int num=5000; num<=14000; num = num + 1000 ){
startTime = System.currentTimeMillis();
method3(num);
lastTime = System.currentTimeMillis();
str = str + "num = "+num+" Took : " + (lastTime - startTime)+" millisecs" + " ";
}
System.out.println(str);
}
}
Output:
--------------Method1-----------------
num = 5000 Took : 4 millisecs
num = 6000 Took : 8 millisecs
num = 7000 Took : 8 millisecs
num = 8000 Took : 12 millisecs
num = 9000 Took : 16 millisecs
num = 10000 Took : 16 millisecs
num = 11000 Took : 24 millisecs
num = 12000 Took : 24 millisecs
num = 13000 Took : 28 millisecs
num = 14000 Took : 32 millisecs
--------------Method2-----------------
num = 5000 Took : 0 millisecs
num = 6000 Took : 0 millisecs
num = 7000 Took : 0 millisecs
num = 8000 Took : 0 millisecs
num = 9000 Took : 0 millisecs
num = 10000 Took : 0 millisecs
num = 11000 Took : 0 millisecs
num = 12000 Took : 0 millisecs
num = 13000 Took : 0 millisecs
num = 14000 Took : 0 millisecs
--------------Method3-----------------
num = 5000 Took : 31 millisecs
num = 6000 Took : 31 millisecs
num = 7000 Took : 47 millisecs
num = 8000 Took : 47 millisecs
num = 9000 Took : 47 millisecs
num = 10000 Took : 47 millisecs
num = 11000 Took : 62 millisecs
num = 12000 Took : 78 millisecs
num = 13000 Took : 79 millisecs
num = 14000 Took : 88 millisecs
Note: I have not drawn any graph for this. But based on these output, you may use any softwarefor drawing the graph for these satistics.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.