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 *n *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 , while 16 billion years is about seconds.)

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

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.