Welcome to our community

Be a part of something great, join today!

Growth of Functions - Big Theta

Lepros

New member
Feb 7, 2012
3
If f(x) if big-theta of g(x), is it also always the case then that g(x) is big-theta of f(x)?
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
Affirmative. (The forum requires a 5-character minimum reply, so I could not just answer "yes".)
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,193

Moo

New member
Feb 12, 2012
26

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
Well, $f(x)=\Theta(g(x))$ means that from some $x_0$ forward and for some positive constants $C_1$ and $C_2$ we have $C_1g(x)\le f(x)\le C_2g(x)$. From this it is clear that $g(x)$ can be similarly bounded by $f(x)$, at least when $f(x)$ and $g(x)$ are (eventually) nonnegative.
 

Moo

New member
Feb 12, 2012
26
But how can you write the double inequality ? We know it's okay if we consider absolute values, but if for example $\forall x>x_0~,~f(x)<0~\text{and}~g(x)>0,~\text{while}~C|f(x)|>g(x)$, what would happen ?

Another equivalent definition (or almost) is that limsup |f/g| < infinity, but if it's 0, couldn't there be a problem ?

I'm basing all this on the wikipedia, so please excuse my ignorance :D


This document ( http://courses.cs.vt.edu/~cs2604/Summer2000/Notes/C03.Asymptotics.pdf ) covers quite a lot of properties related to the big theta. But none of them talk about the equivalence...
 
Last edited:

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
In the Wikipedia page about Big O notation, the definition of $\Theta$ does not involve absolute values, so the relation $f(x)=\Theta(g(x))$ is symmetric. In the PDF document you provided, $\Theta$ is defined only for nonnegative functions. In my experience, $\Theta$ is most often used in algorithm analysis, where resources are usually nonnegative.

For functions that can be negative, the answer depends on the details of the definition of $\Theta$. If it means $C_1|g(x)|\le |f(x)|\le C_2|g(x)|$, then again the relation is symmetric. If it means $C_1g(x)\le |f(x)|\le C_2g(x)$, then, as you say, it does not follow that $|g(x)|\le 1/C_1\cdot f(x)$.
 

Moo

New member
Feb 12, 2012
26