MHB Growth of Functions - Big Theta

[Lepros]

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]

Affirmative. (The forum requires a 5-character minimum reply, so I could not just answer "yes".)

 

[Ackbach]

Affirmative. (The forum requires a 5-character minimum reply, so I could not just answer "yes".)

Changed to 3. Now you can write "No." or "Yes."

 

[Moo1]

Affirmative. (The forum requires a 5-character minimum reply, so I could not just answer "yes".)

Why ?

 

[Evgeny.Makarov]

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.

 

[Moo1]

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 :DThis 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...

 

[Evgeny.Makarov]

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

 

[Moo1]

-

Sorry, I was considering big O and not big theta :( I thought there were the same :(