Editing Big O notation (section)

== Properties ==
If the function {{math|''f''}} can be written as a finite sum of other functions, then the fastest growing one determines the order of {{math|''f''(''n'')}}. For example,
:<math>f(n) = 9 \log n + 5 (\log n)^4 + 3n^2 + 2n^3 = O(n^3) \qquad\text{as } n\to\infty .</math>
In particular, if a function may be bounded by a polynomial in {{mvar|n}}, then as {{mvar|n}} tends to ''infinity'', one may disregard ''lower-order'' terms of the polynomial. The sets {{math|''O''(''n''<sup>''c''</sup>)}} and {{math|''O''(''c''<sup>''n''</sup>)}} are very different. If {{mvar|c}} is greater than one, then the latter grows much faster. A function that grows faster than {{math|''n''<sup>''c''</sup>}} for any {{mvar|c}}  is called ''superpolynomial''.  One that grows more slowly than any exponential function of the form {{math|''c''<sup>''n''</sup>}} is called ''subexponential''. An algorithm can require time that is both superpolynomial and subexponential; examples of this include the fastest known algorithms for [[integer factorization]] and the function {{math|''n''<sup>log ''n''</sup>}}.

We may ignore any powers of {{mvar|n}} inside of the logarithms. The set {{math|''O''(log ''n'')}} is exactly the same as {{math|''O''(log(''n''<sup>''c''</sup>))}}. The logarithms differ only by a constant factor (since {{math|1=log(''n''<sup>''c''</sup>) = ''c'' log ''n''}}) and thus the big O notation ignores that. Similarly, logs with different constant bases are equivalent. On the other hand, exponentials with different bases are not of the same order. For example, {{math|2<sup>''n''</sup>}} and {{math|3<sup>''n''</sup>}} are not of the same order.

Changing units may or may not affect the order of the resulting algorithm. Changing units is equivalent to multiplying the appropriate variable by a constant wherever it appears. For example, if an algorithm runs in the order of {{math|''n''<sup>2</sup>}}, replacing {{mvar|n}} by {{math|''cn''}} means the algorithm runs in the order of {{math|''c''<sup>2</sup>''n''<sup>2</sup>}}, and the big O notation ignores the constant {{math|''c''<sup>2</sup>}}. This can be written as {{math|1=''c''<sup>2</sup>''n''<sup>2</sup> = O(''n''<sup>2</sup>)}}. If, however, an algorithm runs in the order of {{math|2<sup>''n''</sup>}}, replacing {{mvar|n}} with {{math|''cn''}} gives {{math|1=2<sup>''cn''</sup> = (2<sup>''c''</sup>)<sup>''n''</sup>}}. This is not equivalent to {{math|2<sup>''n''</sup>}} in general. Changing variables may also affect the order of the resulting algorithm. For example, if an algorithm's run time is {{math|''O''(''n'')}} when measured in terms of the number {{mvar|n}} of ''digits'' of an input number {{mvar|x}}, then its run time is {{math|''O''(log ''x'')}} when measured as a function of the input number {{mvar|x}} itself, because {{math|1=''n'' = ''O''(log ''x'')}}.

=== Product ===
:<math> f_1 = O(g_1) \text{ and } f_2 = O(g_2) \Rightarrow f_1  f_2 = O(g_1  g_2)</math>
:<math>f\cdot O(g) = O(f g)</math>

=== Sum ===
If <math> f_1 = O(g_1)</math> and <math> f_2= O(g_2) </math> then <math> f_1 + f_2 = O(\max(|g_1|, |g_2|))</math>. It follows that if <math> f_1 = O(g) </math> and <math> f_2 = O(g)</math> then <math> f_1+f_2 \in O(g) </math>.   
=== Multiplication by a constant ===
Let {{mvar|k}} be a nonzero constant. Then <math>O(|k| \cdot g) = O(g)</math>.  In other words, if <math>f = O(g)</math>, then  <math>k \cdot f = O(g). </math>