Editing Big O notation (section)

== Multiple variables ==
Big ''O'' (and little o, Ω, etc.) can also be used with multiple variables. To define big ''O'' formally for multiple variables, suppose <math>f</math> and <math>g</math> are two functions defined on some subset of <math>\R^n</math>. We say
:<math>f(\mathbf{x})\text{ is }O(g(\mathbf{x}))\quad\text{ as }\mathbf{x}\to\infty</math>
if and only if there exist constants <math>M</math> and <math>C > 0</math> such that <math>|f(\mathbf{x})| \le C |g(\mathbf{x})|</math> for all <math>\mathbf{x}</math> with <math> x_i \geq M</math> for some <math>i.</math><ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2009}}, [https://archive.org/details/introductiontoal00corm_805/page/n73 p. 53]</ref>
Equivalently, the condition that <math>x_i \geq M</math> for some <math>i</math> can be written <math>\|\mathbf{x}\|_{\infty} \ge M</math>, where <math>\|\mathbf{x}\|_{\infty}</math> denotes the [[Chebyshev norm]]. For example, the statement
:<math>f(n,m) = n^2 + m^3 + O(n+m) \quad\text{ as } n,m\to\infty</math>
asserts that there exist constants ''C'' and ''M'' such that
:<math> |f(n,m) - (n^2 + m^3)| \le C |n+m|</math>
whenever either <math> m \geq M</math> or <math>n \geq M</math> holds.  This definition allows all of the coordinates of <math>\mathbf{x}</math> to increase to infinity. In particular, the statement
:<math>f(n,m) = O(n^m) \quad \text{ as } n,m\to\infty</math>
(i.e., <math>\exists C \,\exists M \,\forall n \,\forall m\,\cdots</math>) is quite different from
:<math>\forall m\colon~f(n,m) = O(n^m) \quad\text{ as } n\to\infty</math>
(i.e., <math>\forall m \, \exists C \, \exists M \, \forall n \, \cdots</math>).

Under this definition, the subset on which a function is defined is significant when generalizing statements from the univariate setting to the multivariate setting. For example, if <math>f(n,m)=1</math> and <math>g(n,m)=n</math>, then <math>f(n,m) = O(g(n,m))</math> if we restrict <math>f</math> and <math>g</math> to <math>[1,\infty)^2</math>, but not if they are defined on <math>[0,\infty)^2</math>.

This is not the only generalization of big O to multivariate functions, and in practice, there is some inconsistency in the choice of definition.<ref>{{cite web |last1=Howell |first1=Rodney |title=On Asymptotic Notation with Multiple Variables |url=http://people.cis.ksu.edu/~rhowell/asymptotic.pdf |access-date=2015-04-23 |archive-date=2015-04-24 |archive-url=https://web.archive.org/web/20150424012920/http://people.cis.ksu.edu/~rhowell/asymptotic.pdf |url-status=live }}</ref>