2
$\begingroup$

I restate the question: if $ b(x) <f(x) \leq g(x)$ where $b, g \in \Theta(x)$ can we state $f(x) \in \Theta(x)?$ notice that $b(x)< f(x)$ and not $b(x) \leq f(x)$. In other words what if

$f(x) \in \omega(b(x)) $ and

$f(x) \in O(g(x))$

can we state $f(x) \in \Theta(x)$?

$\endgroup$
  • 1
    $\begingroup$ if $b(x)<f(x)$ then $b(x) \le f(x)$ is also true $\endgroup$ – Deep Joshi Mar 17 '17 at 10:46
  • $\begingroup$ Is $\Theta(x)$ the set of functions or the set of values for these functions? $\endgroup$ – Nikos Kazazakis Mar 18 '17 at 9:47
1
$\begingroup$

b(x) is between $c_1·x$ and $c_2·x$ if x is large. g (x) is between $d_1·x$ and $d_2·x$ if x is large. So f (x) is between $c_1·x$ and $d_2·x$ if x is large, which makes it $\Theta(x)$.

$\endgroup$
  • $\begingroup$ Although Deep Joshis' comment was very helpful, this answer proves it by the definition of $\Theta$ notation. Well done! $\endgroup$ – Curious_Dim Mar 18 '17 at 16:52
0
$\begingroup$

If $ \phi(x) \le \psi(x)$, then $\psi \space \epsilon \space \Omega(\phi)$, so $\Omega(\psi) \space \subseteq \space \Omega(\phi)$.


Since $b(x) \le f(x) \le g(x)$, then $\Omega(g) \space \subseteq \space \Omega(f) \space \subseteq \space \Omega(b)$.

And $\Omega(g) \space = \Omega(b)$, so $\Omega(g) \space = \space \Omega(f) \space = \space \Omega(b)$.

Similarly, $\Omega(b) \space = \space \Omega(f) \space = \space \Omega(g)$.

So $\Theta(b) \space = \space \Theta(f) \space = \space \Theta(g)$.

$\endgroup$
0
$\begingroup$

This is much simpler if you use words instead of mathematical stenography:

You have two functions, $b$ and $g$, which draw their values from set $\Theta$. You know that the value of $b$ is always smaller than the value of $g$. Now if you have another function $f$, the values of which are always between the values of $b$ and $g$, $f$ must draw its value from a subset of $\Theta$. Thus, $f(x)\in\Theta$.

$\endgroup$
  • 1
    $\begingroup$ The set $\Theta(x)$ is a set of functions, not a set of values. Even if it were a set of values, your argument won't work unless we know that it is an interval. $\endgroup$ – Yuval Filmus Mar 18 '17 at 8:19
  • $\begingroup$ @YuvalFilmus Is it? Shouldn't that be $\Theta^X$ instead? $\endgroup$ – Nikos Kazazakis Mar 18 '17 at 9:44
  • $\begingroup$ No. It's asymptotic notation, like big O. $\endgroup$ – Yuval Filmus Mar 18 '17 at 9:46
  • $\begingroup$ Ah cool, I'll think about it some more then, thanks! :) $\endgroup$ – Nikos Kazazakis Mar 18 '17 at 9:48

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.