-2
$\begingroup$

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!

$\endgroup$

closed as off-topic by Emil Jeřábek, Gamow, Sasho Nikolov, Hsien-Chih Chang 張顯之, Aryeh Dec 29 '18 at 22:08

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Gamow, Sasho Nikolov, Hsien-Chih Chang 張顯之, Aryeh
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you also provide links to some rigorous proof, from where you have picked this concept? $\endgroup$ – Pranav Chaudhary Dec 27 '18 at 6:55
  • 3
    $\begingroup$ Please, do not answer off-topic questions. $\endgroup$ – Emil Jeřábek Dec 27 '18 at 8:52

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