Complexity of Bogosort...

The really inefficient sorting program we discussed in the class--the one where you find all permutations of n numbers and see if any of them are sorted--is also called

"Bogosort" (or monkeysort etc..)   http://en.wikipedia.org/wiki/Bogosort 

As we saw, it does N* N! comparisons.

We saw that the CS folks' nightmare is exponential complexity, and I mentioned that N*N! is basically exponential complexity. 

To see why this is true, you need to remember Stirling's approximation, which says that for large N, N! is approximatly O(sqrt(N))* (N/e)^N  

(where e is the base of natural logarithms).   See http://en.wikipedia.org/wiki/Stirling's_approximation