Factorial time big-O order


By Alex Allain

Explanation of why there are 100! possible word orders

Assuming that there are 100 distinct words, we can show that there are 100! possible word orders. Consider the case of having 100 slots to fill, each slot being filled by a single word. Take the first slot: you would have 100 words to fill it with; then, the second slot could be filled by any of 99 words, and the third slot, by any of 98 words. Thus, for the first slot, you have 100 options, and for the remaining ninety-nine slots you have, for each of the 100 options, 99! options because for each of the 99 options for the second slot, you have 98! options for the third slot, and so on down the line until you reach the last spot, which must be filled by the remaining word.

A side note about the algorithm

Note that the algorithm suggested can be implemented recursively and used to make permutations of words. You choose a letter, make that the first letter, and then make permutations of the remaining letters that can be appended onto the end of the first letter; each permutation is created by choosing a single letter to append to the previous string and by appending to that newly created prefix the rest of the possible permutations.