1
$\begingroup$

Let's say Ω(g(n)) be a set representing the lower bound and O(g(n)) be another set representing the upper bound for some function f(n).

Can I say that θ(g(n)) is the intersection of these two sets?

The only reasoning I could give for it is that:

  1. Ω(g(n)) is set of all the functions whose running time is at least cg(n) for some c>0.

  2. O(g(n)) is set of all the functions whose running time is at most cg(n) for some c>0.

  3. θ(g(n)) is the set of all the functions whose running time is in between c1g(n) and c2g(n) for some c1,c2>0.

which kind of looks like it is the intersection of both the sets.

$\endgroup$
  • 1
    $\begingroup$ What are your doubts? Why do you think your claim is not true? $\endgroup$ – Discrete lizard Mar 21 at 14:53
  • $\begingroup$ Define $\Theta$ more precisely than "somewhat exactly $cg(n)$ for some $c>0$" and the answer will be immediate. $\endgroup$ – David Richerby Mar 21 at 15:39
  • $\begingroup$ @DavidRicherby done $\endgroup$ – Revolver Mar 21 at 15:50
  • $\begingroup$ So doesn't it more than "kind of look like" the intersection? $\endgroup$ – David Richerby Mar 21 at 15:52

Your Answer

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

Browse other questions tagged or ask your own question.