Sunday, August 29, 2010

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..) 

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's_approximation

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.