## A simple and fast permutation generator (4)

*February 15, 2008 at 12:14 am* *
Leave a comment *

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.

Trackback this post | Subscribe to the comments via RSS Feed