Is $\Theta$ symmetric?

For example if $$f(x)= \Theta (g(x))$$

from the definition of the theta notation, there exist c1 and c2 constants such that

$$c_1 g(x) \le f(x) \le c_2 g(x)$$

then if only we took the constants $1/c_1$ and $1/c_2$ we could say from the definition that

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

Right?

• A different way to see it would be that f=O(g) is equivalent to g=Omega(f), and f=Theta(g) is equivalent to both f=O(g) and f=Omega(g). – chirlu Sep 15 '13 at 19:18

1 Answer

Right, except that the constants are actually $1/c_2$ and $1/c_1$. That is, $$c_1 g(x) \leq f(x) \leq c_2g(x) \Rightarrow \frac{1}{c_2}f(x) \leq g(x) \leq \frac{1}{c_1}f(x)\,.$$ Also, remember that the inequalities only apply for large enough $x$.

• This assumes that both functions attain only positive values (in the limit), i.e. both constants are positive (or negative). If you have mixed signs, the calculations do not work. – Raphael Sep 16 '13 at 8:40
• @Raphael, can you explain why the calculations do not work when signs are mixed? – Imral Dec 16 '20 at 18:59
• @Raphael, In CLRS, it's said at the beginning that all the functions are asymptotically positive. At first, I didn't understand why the functions required to be asymptotically positive, now I kind of have thoughts about it. can you explain the reason for it? – Imral Dec 16 '20 at 19:02
• @Imral For the first comment, what have you tried? Do you remember what happens with _in_equalities if you multiply both sides by a negative factor? – Raphael Dec 17 '20 at 22:13
• @Imral Convenience. It's an introductory textbook; handling only non-negative functions (plus more assumptions, usually) makes many things easier, mathematically speaking. All the terms can be defined in more general cases -- in fact, mathematicians routinely define $O$ on the reals for $x \to x_0 \in \mathbb{R} \cup \{-\infty, \infty\}$. Not only do things get a little more complicated, but all kinds of explicit and implicit "lemmas" used for abusing Landau notation break down in more general settings. – Raphael Dec 17 '20 at 22:17