patternMinor
Is $\Theta$ symmetric?
Viewed 0 times
thetasymmetricstackoverflow
Problem
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?
$$ 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?
Solution
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$.
Also, remember that the inequalities only apply for large enough $x$.
Context
StackExchange Computer Science Q#14339, answer score: 8
Revisions (0)
No revisions yet.