4
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$ – chirlu Sep 15 '13 at 19:18
8
$\begingroup$

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

$\endgroup$
5
  • 4
    $\begingroup$ 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. $\endgroup$ – Raphael Sep 16 '13 at 8:40
  • $\begingroup$ @Raphael, can you explain why the calculations do not work when signs are mixed? $\endgroup$ – Imral Dec 16 '20 at 18:59
  • $\begingroup$ @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? $\endgroup$ – Imral Dec 16 '20 at 19:02
  • $\begingroup$ @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? $\endgroup$ – Raphael Dec 17 '20 at 22:13
  • $\begingroup$ @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. $\endgroup$ – Raphael Dec 17 '20 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.