A simple and fast permutation generator (3)
OK. Watching TV didn’t really work to keep my mind off the problem of the exact runtime order of the algorithm.
After some fiddling around, I came to the following, albeit recursive, formula for the runtime order :
Let G(N) be number of times in the inner loop-code is executed.
The inner loop code is this part :
const size_t V = Pool.front() ; Pool.pop() ; Permutation[ idx ] = V ; Permutate( idx + 1 ) ; Pool.push( V ) ;
It’s this part that does the work, so it will define the time it takes to run the algorithm.
Well as it turns out G(N) = G(N-1)N + N
So, if you know the number of times it takes for N = 3, then you can calculate it for N = 4, etc…
And for N = 1, this number is 1.
How to calculate this number in a non-recursive fashion, I have no idea. It reminds me however of the formula to calculate the number of digits in a Pascal triangle of a certain depth M. This formula is ( M + 1 ) * M / 2. This latter formula resembles the formula for the area of a rectangular triangle in a Cartesian coordinate system with base = M : Area = M*M / 2, which should come as no surprise since a Pascal triangle could be considered a rectangular triangle.
Below you can see a graph of the runtime order with the lower and upper bounds : lower = O(N!), upper = O( NN! ).
In the previous article I stated that O( (N-3)N! ) was an upper bound but in fact any constant c will do to create a formula : (N-c)N! that eventually is an upper bound for the runtime. As soon as N > c, the formula becomes an upper bound. So I made the constant 0, which gives a nicer formula.
The Y-axis is logarithmic.
As you can clearly see, the runtime of the algorithm stays nicely between the stated bounds.
To be continued…
Entry filed under: Command Line.