3

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

Adrian Keister
  • 10,099
  • 13
  • 30
  • 43
Isky Mathews
  • 3,235
  • 11
  • 25

4 Answers4

2

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

Eff
  • 12,989
2

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

Henno Brandsma
  • 242,131
2

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

p0llard
  • 255
1

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

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199