# if $b(x) <f(x) \leq g(x)$ where $b, g \in \Theta(x)$ can we state $f(x) \in \Theta(x)?$

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

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

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

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

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

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

• 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. Mar 18 '17 at 8:19
• @YuvalFilmus Is it? Shouldn't that be $\Theta^X$ instead? Mar 18 '17 at 9:44
• No. It's asymptotic notation, like big O. Mar 18 '17 at 9:46
• Ah cool, I'll think about it some more then, thanks! :) Mar 18 '17 at 9:48