0

I can't seem to find any examples that uses O(n!) time complexity. I can't seem to comprehend how it works. Please help

Jb Geez
  • 77
  • 7

1 Answers1

1

A trivial example is the random sort algorithm. It randomly shuffles its input until it gets it sorted.

Of course, it has strictly no use in the real world, but still, it is O(n!).

EDIT: As pointed out in the comments, this is actually the average time performance of this algorithm. The best-case time complexity is O(1), which happens when the algorithm finds the right permutation right away, and is unbounded in the worst case, since you have no guarantee that the right permutation will come up.

Richard-Degenne
  • 2,892
  • 2
  • 26
  • 43
  • 1
    As per your link, the random version of bogosort is actually unbounded (because randomly generating output may never lead to the correct result). The deterministic version (which enumerates all permutations) is O((n+1)!). While on the subject of permutations, generating all permutations would probably be a better example of an O(n!) algorithm since it has plenty of real-world applications. – Bernhard Barker Jul 31 '17 at 16:40
  • 1
    *randomly generating output may never lead to the correct result* if you use unbounded time this is not true as no permutation has zero as probability among all permutations. Some time the permutation will appear. But the answer is then wrong has there is no bound on the time. – Jean-Baptiste Yunès Jul 31 '17 at 17:08
  • Actually, it's unbounded only in the worst-case scenario. The best-case time complexity is `O(1)`, when it generates the right permutation right away, and `O((n+1)!)` which is equivalent to `O(n!)` in average. And usually, when referring to an algorithm's time complexity, we refer to its average time complexity. I'll update my answer to make that point clearer. – Richard-Degenne Aug 01 '17 at 07:54