2

If $a = O(m)$ and $b = O(n)$, is it true that $a+b = O(m+n)$?

I would try to break it down to $a \le cm$ for some $c$ and $b \le dn$ for some $d$, so if I were to add the right hand side, it would be $cm+dn$, but I don't seem to be able to translate that to a big O/Theta/Omega.

Cookie
  • 13,532
user3511965
  • 141

2 Answers2

1

Recall the definition of "big O" notation: A function (or algorithm, where run time is a function of input size) $f(n)$ is said to be $O(g(n))$ if there is a constant $c$ such that \begin{equation*} \lim_{n\to\infty} \frac{f(n)}{g(n)} = c.\end{equation*}

In your example, you say that $a$ is $O(m)$ and $b$ is $O(n)$, but what you are really saying is that they are both linear (or sub-linear) functions of their input size. So $m$ and $n$ are just two different variable names, and therefore we may as well say that both $a$ and $b$ are $O(n)$, where $n$ is the input size.

Then it is not too hard to see that if \begin{equation*}\lim_{n\to\infty} \frac{a}{n} = c\quad\text{and}\quad \lim_{n\to\infty} \frac{b}{n} = d\end{equation*} for some constants $c$ and $d$, then \begin{equation*} \lim_{n\to\infty} \frac{a+b}{n} = c +d.\end{equation*} This shows that $a+b$ is $O(n)$.

ChocolateAndCheese
  • 1,542
0

Unless $m$ and $n$ define something physical in your problem/algorithm, you could as well call the result O(n). O() notation is more concerned with the variation in powers, eg: $n< n \log(n) < n^2$ etc. So, $(n+m)$ is same as $(n)$

Cookie
  • 13,532
tpb261
  • 802
  • 1
    $m$ is not a constant. – chubakueno May 30 '14 at 04:03
  • of course!!, nor is $n$, right? In fact if they were constants the O() would be O(1), that is constant, not linear. – tpb261 May 30 '14 at 04:06
  • Yes, but you seem to assume that when you say that $O(n+m)=O(m)$ (I think you forgot the $O$). Say, for example, that my algorithm calculates $m+n$ by adding $1$ $m$ times, then adding $1$ $n$ times, and then adding both results. Is the complexity independent of $m$? The formal definition of big $O$ notation may clear some points here :) – chubakueno May 30 '14 at 04:10
  • Here, you seem to be using the first, and I am using the second. I feel the second gives the "sense of Big O" better :D – tpb261 May 30 '14 at 04:22
  • Oh, it is just that in that equation, we are just dealing with one variable. It is true in fact that if $f\in O(g), g \in O(g)$ then $f+g\in O(g+g)=O(2g)= O(g)$. But in our case, we can't factor out a constant in $O(m+n)$. Suppose it is true. Then you have to find a $c$ such that $\forall m,n\ge M$ for some sufficiently large $M$, then $m+n\le cn$. This is impossible. – chubakueno May 30 '14 at 04:40
  • Ok... I'm not clear I follow you. Don't O(m) and O(n) mean that both algorithms are linear (in time, say), and so the sum of the algorithms will also be linear in time? In particular, it is dependent on only one variable - number of inputs. Saying (m+n) is adding more independent variables, right? – tpb261 May 30 '14 at 04:57
  • Yes, the algorithms are definitely linear. But $f(m)=O(m)$ yields more information than just saying that $f$ is linear. It says that $f$ is linear in terms of m. Try to prove that $O(m+n)=O(m)$ for variables $m,n$. You will find yourself in some trouble trying to find the $c$ usch that $m+n\le cn$ for all sufficiently large $m,n$ :) – chubakueno May 30 '14 at 05:03