1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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