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.

RuntimeRelation

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.

Advertisements

Entry filed under: Command Line.

A simple and fast permutation generator (3) A simple and fast permutation generator (6)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Recent Posts

Categories


%d bloggers like this: