2
$\begingroup$

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)

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

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

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

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

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

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.