# What do I get by adding $\Theta(n)$ and $O(n)$?

I know that that $f(n) = O(n)$ means that $n$ is the asymptotically upper bound of $f(n)$ and that $\Theta(n)$ is the asymptotically tight bound of $f(n)$. Still, I'm wondering whether I am allowed to say $\Theta(n) + O(n) = \Theta(n) = O(n)$?

The $O$ and $\Theta$-notation are defined as:

$\Theta(g(n))$ = { $f(n)$: there exists positive constants $c_1$, $c_2$ and $n_0$ such that $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$ for all $n \geq n_0$ }

$O(g(n))$ = { $f(n)$: there exists positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq cg(n)$ for all $n \geq n_0$ }

(this is in the context of analyzing the running time of an algorithm)

-
What is your definition of $\theta$ and $O$? Is $-n = \Theta(n)$ (that is negative $n$)? – Aryabhata Mar 2 '12 at 20:52
Definition added, these are all positive. – Lekensteyn Mar 2 '12 at 21:04
Please be aware of the abuse of notation you commit; see here for details. – Raphael Mar 3 '12 at 13:02
@Raphael Yes I am aware of the actual meaning, thanks. – Lekensteyn Mar 3 '12 at 13:21

As long as you assume that everything is positive (which will usually be the case in context of algorithm analysis) then clearly from $f(n) \in O(n)$ and $g(n) \in \Theta(n)$ it follows that $f(n) + g(n) = \Theta(n)$.

That that class $O(n)$ is closed under addition and that it contains the class $\Theta(n) = O(n) \cap \Omega(n)$ is hopefully quite clear. In other words, since $g(n) = O(n)$, you know that $f(n) + g(n) = O(n)$.

On the other hand, if $f(n) \geq 0$ then $f(n) + g(n) \geq g(n)$, so from $g(n) = \Omega(n)$ you get $f(n) + g(n) = \Omega(n)$. Since now you have both the upper bound and the lower bound, you an conclude that $f(n) + g(n) = \Theta(n)$. If you don't assume $f(n) \geq 0$, then you only get the lower bound $f(n) + g(n) = O(n)$

Be careful with notations like $O(n) + \Theta(n) = \Theta(n)$...

-
I indeed assume $f(n) \geq 0$. What do you mean by your last sentence? – Lekensteyn Mar 2 '12 at 22:45
$O(n)$ is a set: you shouldn't really try to add sets this way. that's what the sentence means I think. – Suresh Venkat Mar 3 '12 at 1:07

Using your definitions, if $a(n) \in \Theta(n)$ and $b(n) \in O(n)$, then $\exists c_1, c_2, n_0, c_3, n_1$ such that $0 \leq c_1 n \leq a(n) \leq c_2 n$ for $n \geq n_0$ and $0 \leq b(n) \leq c_3 n$ for $n \geq n_1$. So then $0 \leq c_1 n \leq a(n) + b(n) \leq c_2 n + c_3 n = (c_2 + c_3) n$ for $n \geq \max\{n_0, n_1\}$. So indeed, $a(n) + b(n) \in \Theta(n) \subset O(n)$.

-
the last sentence is wrong: the set $\Theta(n)$ is NOT a subset of $O(n)$ – Suresh Venkat Mar 3 '12 at 1:08
@Suresh: Why? At least with the given definition, $\Theta(n) = O(n) \cap \Omega(n) \subset O(n), \Omega(n)$. – TMM Mar 3 '12 at 1:23
arggh. sorry. was reading $\Theta$ as $\Omega$ – Suresh Venkat Mar 3 '12 at 6:28