What does $f(x)\in \Theta(g(x))$ mean?

Question

I have recently begun to see examples of people and literature saying statements such as $f(x) \in \Theta(...)$ but what does it mean for one function to be inside or a member of another?

(i.e. I understand that's probably not what it means in this case, but what is this alternative meaning used for functions?)

Answer 1

Unfortunately, there are massive inconsistencies with how big O (and related) notation is used, leading to some confusion.

In this case $\Theta(g(x))$ is the set of functions that are asymptotically bounded below and above by $g$.

Therefore, if $f\in \Theta(g)$ that means that $f$ is in that set, i.e. it is bounded below and above by $g$.

Answer 2

That $\Theta$ is an example of a construct in the area loosely described as "big-O analysis" concerned with how fast functions grow.

The statement $$ f(x) \in \Theta(g(x)), $$ sometimes written $$ f(x) = \Theta(g(x)), $$ means $f$ and $g$ grow at the same rate.

https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/analysis/notations.html

Answer 3

A more common notation is $f = \Theta(g(x))$ (see wikipedia), but as the latter is a set of functions, a more set-theoretical notation is to write $f \in \Theta(g(x))$ instead. It says that $f$ belongs to a certain set of functions vis-à-vis $g$.

Answer 4

Just to formalise the other answers slightly, we say that

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

if and only if

$\exists \: c_1, c_2, N \in \mathbb{R}_{>0}$

such that

$0 < c_1 g(x) \leq f(x) \leq c_2 g(x) \quad \forall x \geq N$.