4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.