If f(n) = Θ(g(n)) does that also mean g(n) = Θ(f(n))?

Question

I'm fairly certain that if f(n) = Θ(g(n)) is true, g(n) = Θ(f(n)) must also be true. However, I'm concerned I might be overlooking something.

Am I correct in thinking that f(n) = Θ(g(n)) then g(n) = Θ(f(n))? or am I overlooking something?

Another way of asking this question: is the $\Theta(\cdot)$ relation symmetric? (Yes, it is.) — Srivatsan, Sep 22 '11 at 21:48

score 10 · Accepted Answer · answered Sep 22 '11 at 20:55

10

You are correct. If $f(n) \in \Theta(g(n))$, then there are constants $c_1, c_2 > 0$ such that for large enough $n$, we have

$$ c_1 g(n) \leq f(n) \leq c_2 g(n)$$.

But this implies $g(n) \leq \frac{1}{c_1}f(n)$ as well as $\frac{1}{c_2}f(n) \leq g(n)$, for large enough $n$.

$$ \frac{1}{c_2} f(n) \leq g(n) \leq \frac{1}{c_1}f(n).$$

Therefore, $g(n) \in \Theta(f(n))$.

answered Sep 22 '11 at 20:55

Shaun Ault

THank you! Exactly my thinking, but was wary about overlooking something. I haven't done any serious Math in about 3 years, so I'm a little rusty. – Wipqozn Sep 22 '11 at 20:58

1 Answers1