Report for Part 2

Transcript of execution of Q follows

[karen@work a8]$ javac Q.java
[karen@work a8]$ java Q
Timing quadratic
Input=850 Average execution time (in milliseconds)=105
Input=1400 Average execution time (in milliseconds)=254
Input=2000 Average execution time (in milliseconds)=517
Input=2900 Average execution time (in milliseconds)=1086
Timing nlogn
Input=19000 Average execution time (in milliseconds)=107
Input=44000 Average execution time (in milliseconds)=261
Input=84000 Average execution time (in milliseconds)=532
Input=150000 Average execution time (in milliseconds)=1009
Timing linear
Input=400000 Average execution time (in milliseconds)=100
Input=1000000 Average execution time (in milliseconds)=247
Input=2000000 Average execution time (in milliseconds)=492
Input=4000000 Average execution time (in milliseconds)=978

		100ms	250ms	500ms	1000ms
Linear	Time	100	247	492	978
Linear	N	400000	1000000	2000000	4000000
NlogN	Time	107	261	532	1009
NlogN	N	19000	44000	84000	150000
Quadratic	Time	105	254	517	1086
Quadratic	N	850	1400	2000	2900

Equations

Linear Substituting 2 pairs of values into the equation

runningTime(n) = An + B;

247 = 1000000 A + B => B = 247 - 1000000 A
978 = 4000000 A + B

Substituting the first equation into the second:

978 = 4000000 A - 1000000 A + 247
978 - 247 = 3000000 A
731/3000000 = A

A = 0.00025
B = -3.3

runningTime(n) = 0.00025 n - 3.3
                                               -7
runningTime(98000) = 20 milliseconds or 2.4 * 10 days

NLogN

Substituting 1 pair of values into the equation

runningTime(n) = A * n * log (n)
                            2
261 = A * 44000 * log (44000)
                     2  
A = 261/(44000 * 15.4) = 0.00039

(Just to confirm the previous result, we try another pair of values.)
1009 = A * 150000 * log (150000);
                   2
A = 0.00039

runningTime(n) = 0.00039 * n * log (n)
                                  2

runningTime(98000) = 633.7 milliseconds or 0.000007 days

Quadratic

Substituting the last 3 pairs of values into the equation

                 2      
runningTime(n)=An + Bn + C
                       
254 = A * 1960000 + B * 1400  + C
517 = A * 4000000 + B * 2000 + C
1086 = A * 8410000 + B * 2900 + C

                                 2
runningTime(n) =  349/2700000 * n - 31/27000 * n + 61/27;

runningTime(98000) = 1,241,296 milliseconds or 0.014 days