3
$\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$

migrated from programmers.stackexchange.com Sep 15 '13 at 20:18

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • $\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$
  • 3
    $\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

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.