Content deleted Content added
Amend section hatnote |
|||
Line 79:
A nonlinear lower bound of <math>\Omega(n\log n)</math> is known for the number of comparisons needed for a [[sorting algorithm]]. Thus the best sorting algorithms are optimal, as their complexity is <math>O(n\log n).</math> This lower bound results from the fact that there are {{math|''n''!}} ways of ordering {{mvar|n}} objects. As each comparison splits in two parts this set of {{math|''n''!}} orders, the number of {{mvar|N}} of comparisons that are needed for distinguishing all orders must verify <math>2^N>n!,</math> which implies <math>N =\Omega(n\log n),</math> by [[Stirling's formula]].
A standard method for getting lower bounds of complexity consists of ''reducing'' a problem to another problem. More precisely, suppose that one may encode a problem {{mvar|A}} of size {{mvar|n}} into a subproblem of size {{math|''f''(''n'')}} of a problem {{mvar|B}}, and that the complexity of {{mvar|A}} is <math>\Omega(g(n)).</math> Without loss of generality, one may suppose that the function {{mvar|f}} increases with {{mvar|n}} and has an [[inverse function]] {{mvar|h}}. Then the complexity of the problem {{mvar|B}} is <math>\Omega(g(h(n))).</math> This is
==Use in algorithm design==
| |||