Binary Mathematical Operations Performed on Different Asymptotic Notations

Question

I'm taking a course on the analysis of algorithms, and I'm trying to understand how different asymptotic notations interact with each other. For example, we learned that

$$O(f(n)) + O(g(n)) = O(f(n) + g(n)) \\ \Omega(f(n)) + \Omega(g(n)) = \Omega(f(n) + g(n)) \\ \Theta(f(n)) + \Theta(g(n)) = \Theta(f(n) + g(n))$$

Based on the definitions for $o$ and $\omega$ notations, as well as how they interact with $O$ and $\Omega$ notations, I determined that

$$o(f(n)) + o(g(n)) = o(f(n) + g(n)) \\ \omega(f(n)) + \omega(g(n)) = \omega(f(n) + g(n))$$

However, I'm unsure of how different notations interact with each other. For example, how to evaluate

$$O(f(n)) + \Theta(g(n))$$

or

$$\Omega(f(n)) + O(g(n))$$

How does one go about evaluating such expressions? And do the rules for addition apply to subtraction and multiplication as well?

Note: This question is not pertaining to any assignments given by the course I'm taking, I'm just trying to fill some of what I feel are holes in my understanding of the material.

Answer 1

For the last two, there isn't really a rule. For instance, take $f(n) = 2n^{3} + 3n^{2}$. Notice that $f(n) = O(n^{3}) + \Theta(n^{2})$. On the other hand, $f(n) \in \Theta(n^3)$.

I would recommend avoiding relying too much on memorizing rules, as I think it will be easy to get tripped up. The Limit Comparison Test (adapted from Calc 2) is a very nice tool for analyzing the functions you will see in Algorithms.

Theorem (Limit Comparison Test): Let $k \geq 0$ be an integer, and denote $\mathbb{Z}_{\geq k} = \{ k, k+1, k+2, \ldots \}$. Let $f, g : \mathbb{Z}_{\geq k} \to \mathbb{R}$ be functions. Suppose that the following limit exists: $$L := \lim_{n \to \infty} \left| \frac{f(n)}{g(n)} \right|.$$

If:

• $0 < L < \infty$, then $f(n) \in \Theta(g(n))$.
• If $L = 0$, then $f(n) \in o(g(n))$.
• If $L = \infty$, then $f(n) \in \omega(g(n))$.

When in doubt, compute the limit.