What's the formal definition of Big-O notation for functions of more than one variable?

For functions of a single totally ordered variable, I already know that $f(n)$ is $O(g(n))$ if and only if $\exists m. \exists c. \forall n. (n \ge m) \rightarrow [ f(n) \le c \cdot g(n) ]$.

What I don't know is the meaning of $O(g(n_1, n_2 \dots n_k))$ for $k > 1$ totally ordered variables. What's the formal definition?

There are many possible definitions; see e.g. Rutanen et al. [1].

Generally speaking, if you define your $O$ over domain $X$, you will need an order relation $\leq$ on $X$. The definition then reads:

$\qquad O(g) = \{ f : X \to \mathbb{R}_{\geq 0} \mid \exists\,x_0 \in X, c \in \mathbb{R}_{>0}.\ \forall\,x\in X.\\
\qquad\qquad\qquad x_0 \leq x \implies f(x) \leq c \cdot g(x) \}.$

So if $X = \mathbb{N}^k$ you can use lexicographic order, element-wise $\leq$, ...

Beware that the properties your $O$ has depend on both the definition and the the order you choose. The outcome may not be as expected.

• A general definition of the O-notation for algorithm analysis by K. Rutanen et al. (2015)

StackExchange Computer Science Q#47873, answer score: 3