Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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)$.

share|improve this answer
    
the last sentence is wrong: the set $\Theta(n)$ is NOT a subset of $O(n)$ –  Suresh Venkat Mar 3 '12 at 1:08
2  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.