Editing Analysis of algorithms (section)

===Orders of growth===
{{main|Big O notation}}
Informally, an algorithm can be said to exhibit a growth rate on the order of a [[Function (mathematics)|mathematical function]] if beyond a certain input size {{mvar|''n''}}, the function {{math|''f''(''n'')}} times a positive constant provides an [[Asymptotic analysis|upper bound or limit]] for the run-time of that algorithm.  In other words, for a given input size {{mvar|''n''}} greater than some {{mvar|''n''}}<sub>0</sub> and a constant {{mvar|''c''}}, the run-time of that algorithm will never be larger than {{math|''c'' × ''f''(''n'')}}.  This concept is frequently expressed using Big O notation.  For example, since the run-time of [[insertion sort]] [[quadratic growth|grows quadratically]] as its input size increases, insertion sort can be said to be of order {{math|''O''(''n''<sup>2</sup>)}}.

Big O notation is a convenient way to express the [[Best, worst and average case|worst-case scenario]] for a given algorithm, although it can also be used to express the average-case &mdash; for example, the worst-case scenario for [[quicksort]] is {{math|''O''(''n''<sup>2</sup>)}}, but the average-case run-time is {{math|''O''(''n'' log ''n'')}}.