How Fast Do Factorials Grow?

Sometimes it’s hard to grasp just exactly how fast certain rapidly increasing functions – like exponentials and factorials – actually grow.  This was brought home to me a few years ago when I wrote some code for solving a problem whose size grew factorially.  I don’t remember now exactly how fast it took to solve some of the smaller instances, but the numbers below illustrate the general idea.

Suppose you write a program that will generate all possible shufflings of a deck of n cards and then search through each shuffling counting how many have a particular property.  If it takes one second for the program to return the answer when there is one card in the deck, how large a deck can you test before the semester runs out?

Since there are n! different shufflings for a deck of cards, the time it takes for the program to run is factorial in the input size. The table below gives these times for the smaller deck sizes.

Deck Size Time
1 card 1 second
2 cards 2 seconds
3 cards 6 seconds
4 cards 24 seconds
5 cards 2 minutes
6 cards 12 minutes
7 cards about an hour and a half
8 cards about 11 hours
9 cards about 4 days
10 cards 6 weeks
11 cards about 15 months
12 cards about 15 years
13 cards about 200 years
14 cards about 2800 years

The largest deck you could test in a semester would be only a 10-card deck.  In a lifetime, you would only have time to test a 12-card deck.

In fact, if the universe is about 16 billion years old, and your program started running when the universe began, then up to now it would have had time to test a deck of at most 19 cards. (The value of 19! is approximately 1.2 \times 10^{17}, while 16 billion years is about 5.1 \times 10^{17} seconds.)

Advertisements
This entry was posted in arithmetic, asymptotics. Bookmark the permalink.

2 Responses to How Fast Do Factorials Grow?

  1. I’m trying to imagine a property for which it would take a computer a whole second to determine on a 1-card deck!

    • mzspivey says:

      Yeah, I needed a place to start with the counting for this blog post, and one second was a nice round number. For the actual problem I was considering, I think it took about a minute for the 10-card deck. (I didn’t code the smaller decks because I could do those by hand.) Extrapolating from there, the semester was going to end before the computer could finish with the 16-card deck.

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