Fibonacci is n(i) = n(i-1) + n(i-2). Factorial is n! = n * n-1 * n-2 * ... * 2 * 1. In the second sentence, you might have wanted "lg(n!) is approximately n lg

Fibonacci is n(i) = n(i-1) + n(i-2). Factorial is n! = n * n-1 * n-2 * ... * 2 * 1. In the second sentence, you might have wanted "lg(n!) is approximately n lg n". That would be a good reason for needing n lg n comparisons to distinguish between the n! permutations. I have edited this comment as my understanding of the parent comment developed >_>