What's the formal definition of Big-O notation for functions of more than one variable?
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}_{&gt;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)