EmptyCrate Software. Travel. Stuff.

In this article I'm going to break down the math for one of our examples, so we can see how the process works.

First of all, we will run our exponential function with the run_timing application for several different values of N.

Looking back at the data from yesterday:

jason@ubuntu:~/Programming$ ./run_timing ./two_to_the_n 20 25 26 27 28 29 30
20: 36437
25: 507890
26: 807668
27: 1584727
28: 3093271
29: 6157129
30: 12325504
Early in analysis: 
Time To Execute: 777300
Velocity: -442890
Acceleration: 422510
Jerk: 396000
Your run time is accelerating, this is bad, indicating polynomial complexity.
Your run time has positive jerk, this means that your acceleration is increasing, indicating possible exponential complexity (very bad).
-------------------
Later in analysis: 
Time To Execute: 6.6098e+06
Velocity: 4.4151e+06
Acceleration: 2.0065e+06
Jerk: 396000
Your run time is accelerating, this is bad, indicating polynomial complexity.
Your run time has positive jerk, this means that your acceleration is increasing, indicating possible exponential complexity (very bad).

The function generated by octave from the timing data is: [math]t=66000n^3-4738700n^2+112740000n+887360000[/math]. This function estimates for us how long (in nanoseconds) it will take to execute our [math]2^n[/math] complexity program. For example, the function estimates that it will take 62 seconds to execute with a value of [math]n=34[/math].

The first derivative of the function represents the "velocity" of the function. That is, how quickly the runtime is changing. [math]v=198000n^2-9477400n+11274000[/math]. This is not terribly useful for our analysis.

The second derivative represents the acceleration of the function. That is, how quickly the velocity is changing. [math]a=396000n-9477400[/math]. Runtime acceleration indicates an algorithm which is becoming less efficient as N increases.

The third derivative represents the "jerk" of the function. The jerk is how quickly the acceleration is changing. An increasing acceleration means that the inefficiency of the algorithm is continuously increasing as N increases. This is the worst case scenario. [math]j=396000[/math].

Using Maxima we are able to plot the known complexity, [math]t=2^n[/math] against its first 3 derivatives, [math]v=\log(2) 2^n[/math], [math]a=\log(2)^2 2^n[/math], and [math]j=\log(2)^3 2^n[/math] and compare it to our analysis.
2^n Algorithm Complexity: Image of 2^n graphed along with its first 3 derivatives

We can see from the graph that this algorithm has increasing velocity, acceleration and jerk, its jerk is even accelerating!

Our generated function is a third order polynomial ([math]x^3[/math] being the highest power). Because of this we know that by the third derivative we will only have a constant left, which is what we showed a few paragraphs up: [math]j=396000[/math]. So, we are not looking at the shape of our jerk, only the value that it has. Remember, positive jerk means increasing acceleration.

The 4 graphs of our function (function, 1st, 2nd and 3rd derivatives):
Time
Velocity
Acceleration
Jerk

Interesting things to note:

1. We did not provide any data from 20-25 to Octave so it was free to make that initial wave in the function that did not actually exist. This is a common problem with trending analysis. The computer can only fit the data you give it, it has to make an estimate at the interpolated parts.
2. The first three graphs show the characteristic growth as N increases.
3. The fourth graph shows positive Jerk, the characteristic of an exponential function that we were hoping to find.
4. Since we only told the polyfit function of Octave to generate a 3rd order polynomial, the value of jerk will always be a constant. It would be possible to have polyfit generate a higher order function, but through experimentation it seems that higher order functions are less able to represent the common cases of algorithm complexity. I could be wrong about this.