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?

Improve this question
$\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, 2013 at 19:18

1 Answer 1

Reset to default
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$.

Improve this answer
$\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, 2013 at 8:40
  • $\begingroup$ @Raphael, can you explain why the calculations do not work when signs are mixed? $\endgroup$
    – Alparslan
    Dec 16, 2020 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$
    – Alparslan
    Dec 16, 2020 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, 2020 at 22:13
  • 1
    $\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, 2020 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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