# Is $O$ contained in $\Theta$?

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

• 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.. – Ran G. Aug 17 '12 at 15:13
• I think you're right, it seems like a mistake. – Yuval Filmus Aug 17 '12 at 15:25
• What do you mean by the notation $\subset$: subset or proper subset? I would advise to use $\subseteq$ or $\subsetneq$ to avoid confusion. – A.Schulz Aug 18 '12 at 11:46

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