Editing Time complexity (section)

== Factorial time ==

An algorithm is said to be '''factorial time''' if ''T(n)'' is upper bounded by the [[factorial function]] ''n!''. Factorial time is a subset of exponential time (EXP) because <math> n! \leq n^n = 2^{n \log n}= O \left(2^{n^{1 + \epsilon}} \right)</math> for all <math>\epsilon > 0</math>. However, it is not a subset of E.

An example of an algorithm that runs in factorial time is [[bogosort]], a notoriously inefficient sorting algorithm based on [[trial and error]].  Bogosort sorts a list of ''n'' items by repeatedly [[shuffling]] the list until it is found to be sorted. In the average case, each pass through the bogosort algorithm will examine one of the ''n''! orderings of the ''n'' items.  If the items are distinct, only one such ordering is sorted. Bogosort shares patrimony with the [[infinite monkey theorem]].