4
$\begingroup$

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))$ ?

please guide me .

$\endgroup$
2
$\begingroup$

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.

See this article for a discussion on the subject.

$\endgroup$
2
$\begingroup$

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))$.

$\endgroup$
  • $\begingroup$ mathwiki.cs.ut.ee/asymptotics/04_multiple_variables what do you say about this one ? $\endgroup$ – Becoming Algebra Mar 17 at 11:45
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Mar 18 at 15:59
  • $\begingroup$ I am surprised that you have accepted the other answer that does not analyze your question closely. In particular, I suspect its author did not even bother to check the last several statements in the question. $\endgroup$ – Apass.Jack Mar 18 at 16:00
  • $\begingroup$ Also, the article mentioned in the other answer is, I believe, superseded by the paper mentioned in this answer. (Of course, it is still a nice article to read.) $\endgroup$ – Apass.Jack Mar 18 at 16:08
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Mar 20 at 15:53

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.