"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

## No comments:

## Post a Comment

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