3
$\begingroup$

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?

  • 0
    Another way of asking this question: is the $\Theta(\cdot)$ relation symmetric? (Yes, it is.)2011-09-22

1 Answers 1

8

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

  • 0
    THank you! Exactly my thinking, but wa$s$ wary about overlooking something. I haven't done any serious Math in about 3 years, so I'm a little rusty.2011-09-22