11
$\begingroup$

So I have this question to prove a statement:

$O(n)\subset\Theta(n)$...

I don't need to know how to prove it, just that in my mind this makes no sense and I think it should rather be that $\Theta(n)\subset O(n)$.

My understanding is that $O(n)$ is the set of all functions who do no worse than $n$ while $\Theta(n)$ is the set of all functions that do no better and no worse than n.

Using this, I can think of the example of a constant function say $g(n)=c$. This function will surely be an element of $O(n)$ as it will do no worse than $n$ as $n$ approaches a sufficiently large number.

However, the same function $g$ would not be an element of $\Theta(n)$ as g does do better than $n$ for large $n$... Then since $g \in O(n)$ and $g \not\in \Theta(n)$, then $O(n)\not\in\Theta(n)$

So is the question perhaps wrong ? I've learnt it is dangerous to make that assumption and usually I have missed something, I just can't see what it might be in this case.

Any thoughts ? Thanks a lot..

$\endgroup$
  • 5
    $\begingroup$ Think of $f=0$. then $f=O(n)$ but $f\not=\Theta(n)$. So "$O(\cdot)$" is a weaker demand, thus it contains more functions.. $\endgroup$ – Ran G. Aug 17 '12 at 15:13
  • 5
    $\begingroup$ I think you're right, it seems like a mistake. $\endgroup$ – Yuval Filmus Aug 17 '12 at 15:25
  • 3
    $\begingroup$ What do you mean by the notation $\subset$: subset or proper subset? I would advise to use $\subseteq$ or $\subsetneq$ to avoid confusion. $\endgroup$ – A.Schulz Aug 18 '12 at 11:46
11
$\begingroup$

At the suggestion of Raphael, I have turned a previous comment into this answer.

It is not true that $O(f(n)) \subset \Theta(f(n))$. In fact, $\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))$, by definition. So we have $\Theta(f(n)) \subset O(f(n))$.

$\endgroup$
4
$\begingroup$

Think about it this way: every function that does "no worse than n" and "no better than n" is also a function that does "no worse than n". The "no better than n" part is just an additional constraint. This is a straightforward application of the logical rule that says: $x \wedge y \implies x$. By this reasoning, all functions that are in the set $\Theta(n)$ are also members of the set $O(n)$.

$\endgroup$

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.