Report for cubicTime
Transcript of execution of Q2 follows
[karen@work a8]$ javac Q2.java
[karen@work a8]$ java Q2
Input=72 Average execution time (in milliseconds)=102
Input=100 Average execution time (in milliseconds)=243
Input=125 Average execution time (in milliseconds)=475
Input=160 Average execution time (in milliseconds)=1009
| 100ms | 250ms | 500ms | 1000ms |
| Cubic |
Time | 102 | 243 | 475 | 1009 |
| N | 72 | 100 | 125 | 160 |
Substituting the first 4 pairs of values into the equation
3 2
runningTime(n)=An +Bn +Cn+D
we end up with the following 4 equations in 4 unknowns
- 373248 A + 5184 B + 72 C + D = 102
- 1000000 A + 10000 B + 100 C + D = 243
- 1953125 A + 15625 B + 125 C + D = 475
- 4096000 A + 25600 B + 160 C + D = 1009
Solving these for A,B,C,D gives the following polynomial
10873 3 20983 2 -5793587 474165
runningTime(n) = -------- n + ------- n + -------- n + ------
48972000 1484000 2448600 4081
Yes, these numbers are ugly, but that's what we get in the real world.
After making sure I really did get the right numbers by evaluating
runningTime(160) again to get 1009, I evaluted runningTime(500)= 30221,
and then ran the cubic method with n=500 to get an average execution
time of 31102 milliseconds
which is pretty close to what we would expect.
Finally, using the running time polynomial above, if we ran cubicTime(98000), it would take
runningTime(98000) seconds to execute. That is,
10873 3 20983 2 -5793587 474165
runningTime(98000) = -------- 98000 + ------- 98000 + -------- 98000 + ------
48972000 1484000 2448600 4081
This works out to 209,103,555,000 milliseconds or around 2420 days.