A simple and fast permutation generator (4)
Hi folks, here’s Runtime Joe again.
If you analyze the algorithm intuitively, like I did a gazillion times in the past few hours, you could say that the number of times the inner loop-code executes should be well…N!.
Here’s why. Let’s say the permutation size is 4.
I loop 4 times, these 4 times I recursively call a function that loops 3 times, which in turn calls a function that loops 2 times, etc…
So the number of inner loop code executions should intuitively be : 4 x 3 x 2 x 1 = 4!.
But intuition is not everything.
If you try reason just a tad beyond this, you can also see that recursively calling the child N times, within your N-times loop, causes the child to be executed N times. So your inner loop executes N times, but his as well. So that’s where the + N part comes from in the recursive formula.
So total number of inner loop executions = ( main parent loop : N times ) + ( recursive call : N times x ( Whatever number of times the child executes the inner loop ) ). This looks wacky, buy it is in fact logical : calling a child function N times that executes the same code as the parent, gives you 2N times that code. Suppose the child does not loop, like when N = 2. Then the parent executes the inner loop code 2 times, and calls a function to execute that code also 2 times, which gives 4 times in total.
All of this leads to a value larger than N!.
Since I had the values nicely in Excel, I decided to see whether there was some linear relation between the recursive runtime formula value and the N! values.
This is what I came up with.
It’s late, so maybe I going completely bonkers but anyway this is it.
As you can see the ratio converges to 2,718281828…
So the best formula I can come up with at the moment for the runtime big O notation is O( 2,718281828 N! ).
Which is kind of silly since you can drop the constant factors from the order, and so it becomes O(N!) again.
Still we don’t know a nice exact formula for the number of times the inner loop executes, but we do now have a reasonably reliable runtime order.
Entry filed under: Command Line.