Order Mistake Definition in CLRS

On page 53 or CLRS it has said :

We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function $$g(n,m)$$, we denote by $$O(g(n,m))$$ the set of functions \begin{align} O(g(n,m)) = \{ f(n,m) : &\text{there exist positive constants }c, n_0,\text{ and } m_0 \\ &\text{ such that } 0 \le f(n,m) \le cg(n,m)\\ &\text{ for all } n\ge n_0\text{ or } m \ge m_0 \} \end{align}

I think this definition has a problem cause if $$n \ge n_0$$ for some constant $$n$$ then we don't need to grow $$m$$! I feel something is Wrong! It must be the word "and" instead of "or" for example : $$f(x , y ) = x^2 + y^2$$
$$g_2(x,y) = x^2 + y$$
$$g_1(x,y) = x^2 + x*y$$

by the definition $$f(x,y)$$ is $$O(g_1(x,y))$$ ! or even $$f(x,y)$$ is $$O(g_2(x,y))$$ ?

• Feb 23, 2022 at 17:29

Well, there is not really a completely satisfying way to have the big-O Notation with multiple variables. Therefore CLRS present one way of a generalization. Putting an and instead of the or would give a new definition with other problems.

It looks like you misunderstood the definition.

To be more precise, the definition is read as the following.

\begin{align} O(g(n,m)) = \{ f(n,m) : &\text{there exist positive constants }c, n_0,\text{ and } m_0 \\ &\text{ such that } 0 \le f(n,m) \le cg(n,m)\\ &\text{ for all } (n,m)\text{ such that }n\ge n_0\text{ or } m \ge m_0 \} \end{align}

$$f(x,y)\not\in O(g_1(x,y))$$

For the sake of contradiction, suppose $$f(x,y)\in O(g_1(x,y))$$. Then there exist positive constants $$c$$, $$n_0$$, and $$m_0$$ such that $$0 \le f(n,m) \le cg(n,m)$$ for all $$n\ge n_0$$ or $$m \ge m_0$$.

$$\lim_{m\to\infty}\frac{f(n_0,m)}{g_1(n_0,m)}=\lim_{m\to\infty}\frac{n_0^2 + m^2}{n_0^2 + m}=\lim_{m\to\infty}\frac{\frac{n_0^2}m + m}{\frac{n_0^2}m + 1}=\lim_{m\to\infty}\frac{m}{1}=\infty$$

So, there exists $$m_1\ge m_0$$, such that $$f(n_0,m_1) > cg_1(n_0,m_1)$$. This contradicts to the condition that $$f(n,m) \le cg_1(n,m)$$ for all $$n\ge n_0$$. Q.E.D.

There is no way to define the big-$$O$$ notation for functions on more than one variable in a way that implies all properties commonly used in algorithm analysis. You can read this long paper by Kalle Rutanen, March 15, 2018, O-notation in Algorithm Analysis (updated) for details. So one has to be somewhat wary using the big-O notation in the case of multiple variables.

On the other hand, if the functions inside the notation are nondecreasing in each variable, then most properties used in algorithm analysis do hold for some natural definitions of the big $$O$$-notation for multivariate functions. This is the case in the question, when we can be more comfortable. In fact, that paper claims that "computer scientists have used the O-notation correctly intuitively" by providing "a solid mathematical foundation" (quoted from its chapter 7, conclusion).

Exercise 1. Show that $$g_1(x,y)\in O(f(x,y))$$ and $$g_2(x,y)\in O(f(x,y))$$

Exercise 2. Show that $$f(x,y)\not\in O(g_2(x,y))$$.

Exercise 3. Show that $$f(x,y)\in O(2x^2+3y^4)$$ and $$f(x,y)\in O(\max(x^2,y^2))$$.

• In fact, the definition of big $O$ for functions of two variables at mathwiki.cs.ut.ee is basically the same as the definition given in the same book introduction to algorithms but in its second edition. There can be a lot more to say about these two definitions. Mar 18, 2019 at 15:59
• I could show why the definition was changed from "$n\ge n_0$ and $m\ge m_0$" to "$n\ge n_0$ or $m\ge m_0$" if you are interested. Mar 20, 2019 at 15:53