I was reading “Introduction to Algorithms” by CLRS and it says
Note that f(n) = Θ(g(n)) implies f(n) = O(g(n)) since Θ notation is a stronger notation than O notation. Written set theoretically, we have Θ(g(n)) ⊆ O (g(n)) .
This means that Θ is a subset of O . Both the statements seem contradictory.
Lets refactor and reword these statements for ease of thought.
Let $A(n)$ be $Θ(g(n))$.
Let $B(n)$ be $O(g(n))$.
Note that $A$ implies $B$ because $A$ is stronger than $B$.
This means for $A$ to be fulfilled we have to fulfill the criteria of $B$ and more. Therefore $A$ being fulfilled implies $B$ must also be.
Written set theoretically, we have the set of functions that fulfill the criteria of $A$ are a subset of the functions that fulfill the criteria of $B$.
Well this is not contradictory, but actually equivalent in a sense to the last statement which showed that $A$ has the criteria of $B$ and more.
From our understanding of this point we can determine that: All the functions that fulfill the criteria of $A$ fulfill $B$, but not all functions that fulfill the criteria of $B$ fulfill the criteria of $A$.
This is really an equivalent statement to: The functions that fulfill the criteria of $A$ are a subset of the functions that fulfill the criteria of $B$ because the second set contains the first.
And therefore $\Theta(g(n))\subseteq O (g(n))$ is true, and it is equally true that $f(n) = \Theta(g(n))$ implies $f(n) = O(g(n))$ without any contradiction.
Furthermore this makes sense with the definition for $\Theta(g(n))$ which states that: $f(n)\in \Theta(g(n))$ if and only if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$. Clearly by this definition, $f(n) \in Θ(g(n))$ does imply $f(n) \in O(g(n))$, and $\Theta(g(n))$ is clearly a subset of $O(g(n))$ as well.
= signs are confusing. f(n) = Θ(g(n)) implies f(n) = O(g(n)) without any contradiction can be true only if Θ(g(n)) = O(g(n)). Did you (and the CLRS authors) mean f(n) ∈ Θ(g(n)) implies f(n) ∈ O(g(n))?
$\endgroup$
= because the author did. In these notations however, there is a convention that = may be used instead of ∈ to mean the same thing. It bothers me too though. Since the aim of my answer is to show that what the author said is correct, it didn't seem right to modify the notation on him.
$\endgroup$
Commented
Jun 17, 2016 at 22:39
= is because we can say that "if two things are equal to something, then they are equal to each other", in the context of an asymptotic relation, this applies, though it is the same property of equality that would make us turn our nose at this when taken at a more general context. Using subset however, does not imply this relation. I would honestly be more ok with the 'equivalence' symbol (≡), which could imply this relation under a condition. As 5 ≡ 9 in mod 4, 3x ≡ 5x for big O analysis.
$\endgroup$
Commented
Jun 17, 2016 at 23:02
No contradiction here. For simplicity, consider this example. You have a function, $f(n)$, if we say $f$ is $O(n^2)$ that would mean that $f$ is asymptotically less than a quadratic function. But if we know that $f$ is in fact linear, that would imply even stronger statement that $f$ is actually $\Theta(n)$. But linear functions are obviously one of the many functions bounded by quadratic function (such as $\log$, $n^{3/2}$, etc), hence it is a subset.
