<p>The intersection one is correct, and I'll provide a not-so-rigorous explanation why.</p>

<p>We can think of <span class="math-container">$\mathcal O(g(n))$</span> as being a <em>family</em> of functions: those which increase either slower than or as fast as <span class="math-container">$g(n)$</span>. For example, if <span class="math-container">$g(n) = n^2$</span> then the function <span class="math-container">$f(n) = n$</span> satisfies <span class="math-container">$f(n) \in \mathcal O(g(n))$</span>. </p>

<p>Similarly, <span class="math-container">$ \Omega(g(n))$</span> is also a function family of the functions which increase either faster or as fast as <span class="math-container">$g(n)$</span>. Again if <span class="math-container">$g(n) = n^2$</span> then <span class="math-container">$f(n) = n^3$</span> satisfies <span class="math-container">$f(n) \in \Omega(g(n))$</span>. </p>

<p>Now <span class="math-container">$\Theta(g(n))$</span> is (yet another) function family of the ones which increase as fast as <span class="math-container">$g(n)$</span> (but not faster or slower!) For example <span class="math-container">$g(n) = n^2$</span> and <span class="math-container">$f(n) = 2n^2+3n+1$</span> satisfy <span class="math-container">$f(n)\in \Theta(g(n))$</span>. </p>

<p>If <span class="math-container">$\Theta(g(n)) = \mathcal O(g(n)) \cup \Omega(g(n))$</span>, then we would have that <span class="math-container">$f(n) = n \in \Theta(g(n))$</span> for the same <span class="math-container">$g(n)$</span> as before, which is not true. On the other hand, <span class="math-container">$\Theta(g(n)) = \mathcal O(g(n)) \cap \Omega(g(n))$</span> would imply that <span class="math-container">$\Theta(g(n))$</span> only contains functions which increase at the same speed as <span class="math-container">$g(n)$</span>, which is what we want.</p>

CC BY-SA 4.0
2018-12-27T06:55:31.417Z
Can you also provide links to some rigorous proof, from where you have picked this concept?
Pranav Chaudhary
CC BY-SA 4.0
2018-12-27T08:52:26.667Z
Please, do not answer off-topic questions.
Emil Jeřábek
CC BY-SA 4.0
2018-12-27T06:44:56.247Z
2018-12-27T06:44:56.247Z
Misha Ivkov
<p>While studying the complexity theory, I encountered a question which is as follows:-</p>

<p>Which one of the following is correct?</p>

<p>1) θ(g(n)) = O(g(n)) ∩ Ω(g(n))</p>

<p>2) θ(g(n)) = O(g(n)) ∪ Ω(g(n))</p>

<p>I know what, θ and Ω represent. But, I am totally confused with the union and intersection operations performed between them. What does it actually mean and what is the correct answer? Thanks for the help!</p>

<asymptotics>
Which one of the following is the correct asymptotic notation?
Pranav Chaudhary
# Which one of the following is the correct asymptotic notation?

(Asked by: username_0 on 2018-12-27)

While studying the complexity theory, I encountered a question which is as follows:-

Which one of the following is correct?

1) θ(g(n)) = O(g(n)) ∩ Ω(g(n))

2) θ(g(n)) = O(g(n)) ∪ Ω(g(n))

I know what, θ and Ω represent. But, I am totally confused with the union and intersection operations performed between them. What does it actually mean and what is the correct answer? Thanks for the help!

**Tags:** asymptotics


---

## 1 answers

### Answer by username_1 on 2018-12-27. Score: 1 | Accepted answer

The intersection one is correct, and I'll provide a not-so-rigorous explanation why.

We can think of $\mathcal O(g(n))$ as being a *family* of functions: those which increase either slower than or as fast as $g(n)$. For example, if $g(n) = n^2$ then the function $f(n) = n$ satisfies $f(n) \in \mathcal O(g(n))$.

Similarly, $ \Omega(g(n))$ is also a function family of the functions which increase either faster or as fast as $g(n)$. Again if $g(n) = n^2$ then $f(n) = n^3$ satisfies $f(n) \in \Omega(g(n))$.

Now $\Theta(g(n))$ is (yet another) function family of the ones which increase as fast as $g(n)$ (but not faster or slower!) For example $g(n) = n^2$ and $f(n) = 2n^2+3n+1$ satisfy $f(n)\in \Theta(g(n))$.

If $\Theta(g(n)) = \mathcal O(g(n)) \cup \Omega(g(n))$, then we would have that $f(n) = n \in \Theta(g(n))$ for the same $g(n)$ as before, which is not true. On the other hand, $\Theta(g(n)) = \mathcal O(g(n)) \cap \Omega(g(n))$ would imply that $\Theta(g(n))$ only contains functions which increase at the same speed as $g(n)$, which is what we want.

> **Comments:**
> **username_0**: Can you also provide links to some rigorous proof, from where you have picked this concept?  
> **username_2**: Please, do not answer off-topic questions.  

---

