1
$\begingroup$

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.

$\endgroup$

migrated from stackoverflow.com Jun 16 '16 at 19:26

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Θ is asymptotically tight bound for f(n) having both lower and upper bound. Whereas, O notation gives an upper bound on a function. @MattBall $\endgroup$ – shivani1007 Jun 16 '16 at 16:19
  • 1
    $\begingroup$ What part seems contradictory? $\endgroup$ – David Richerby Jun 16 '16 at 19:54
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jun 17 '16 at 11:28
  • $\begingroup$ Which two statements? $\endgroup$ – Raphael Jun 17 '16 at 11:28
  • 1
    $\begingroup$ Maybe check out our reference question $\endgroup$ – adrianN Jun 17 '16 at 15:39
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The = 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$ – Jerry101 Jun 17 '16 at 22:30
  • 1
    $\begingroup$ @Jerry101 Agreed. I used = 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$ – rp.beltran Jun 17 '16 at 22:39
  • 1
    $\begingroup$ Wow. That convection is awful, and perhaps the key to the OP's question. $\endgroup$ – Jerry101 Jun 17 '16 at 22:41
  • 2
    $\begingroup$ @Jerry101 Like I said, I don't like it either, but there a point to it. The reason we can use = 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$ – rp.beltran Jun 17 '16 at 23:02
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy