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