Problem on time complexity

Question

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.

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

Answer 2

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