Set relationship between Big-Oh and Theta notations

Question

I was reading "Introduction to Algorithms" by CLRS and it says that:

We write $f(n) = O(g(n))$ to indicate that a function $f(n)$ is a member of of the set $O(g(n))$. Note that $f(n) = \Theta(g(n))$ implies $f(n)=O(g(n))$, since $\Theta$-notation is a stronger notion than $O$ notation. Written set-theoretically, we have $\Theta(g(n)) \subseteq O(g(n))$.

Q1: What do the authors mean by strong notion? What is strong notion, when we use it, how does it help us (here) knowing one implication is stronger than the other and how does it affect when creating implication.
Q2: It seems contradictory in a sense by saying that $\Theta$ is stronger notion than $O$ and then writing $\Theta(g(n)) \subseteq O(g(n))$.How to deduce and then interpret the second sentence from the first?

I would appreciate your answers.

Answer 1

In general, a proposition $P$ is said to be stronger than $Q$ if $P$ implies $Q$ ( symbolically, $P\Rightarrow Q$) and $NOT$( $Q$ implies $P$). In the example at hand, $f \in \Theta(g) \Rightarrow f \in \mathcal{O}(g)$ , so that $f \in \Theta(g)$ is a stronger assertion than $f \in \mathcal{O}(g)$.

Answer 2

When you say $f(n) = \mathcal{O}(g(n))$, it means that $g$ is an upper bound for $f$, up to a constant. So $f(n) \leq c \cdot g(n)$ for all $n \geq k$, and for some $c_1$. $c_1$ and $k$ are fixed. Now we must introduce $\Omega$. If $f(n) = \Omega(g(n))$, then $g$ is a lower bound for $f$, up to a constant. So $f(n) \geq c_2\cdot g(n)$.

Now, when we say $f(n) = \Theta(g(n))$, then $f \in \mathcal{O}(g(n))$ and $f \in \Omega(g(n))$. So $\Theta$ is a tight bound, while $\mathcal{O}$ is only an upper bound. Thats what is means by stronger. $f \in \Theta(g) \iff c_2\cdot g <= f <= c_1\cdot g$. When the author says $\Theta(g(n)) \subseteq \mathcal{O}(g(n))$, they mean that whenever $f \in \Theta(g)$, $f$ is also in $\mathcal{O}(g)$

Another thing worth noting is that a lot of people assume we only use $\mathcal{O}$ for worst case analysis and $\Omega$ for best case. This is not the case. A tight bound is much more useful. Usually, use both of them (as in use $\Theta$) for both best case and worst case (and average case) analysis.

Answer 3

"stronger notation" from first sentence simply means subset from second - it is same.