Big Omega -- n, n + 100

Question

Given $f(n) = n$ and $g(n) = n + 100$, it seems that f(n) is $O(g(n))$ when $C = 1$ and $k= 0$. That is, for every $n$ from $0$ to infinity, g(n) is strictly larger than f(n).

Now, concerning $\Omega$ notation, it seems that we could also say that $g(n)$ is $\Omega(f(n))$ because there is some $C = 101$ and $k = 1$ such that g(n) will always be smaller or equal to $f(n)$.

Is this sufficient to also say that $f(n)$ is $\theta(g(n))$, or do the $K$ and $c$ values have to be the same in both the $O$ case and the $\Omega$ case?

UPDATE: I think I have this switched around. I would need to show that $f(n)$ is also $\Omega(g(n))$. I think this is possible if $C = 0$.

Is it generally true that if $f(x)$ is $O(g(x))$, then $f(x)$ is $\theta(g(x))$ when $C = 0$?

Answer 1

UPDATE: I think I have this switched around. I would need to show that f(n) is also Ω(g(n)). I think this is possible if C=0. Is it generally true that if f(x) is O(g(x)), then f(x) is θ(g(x)) when C=0?

You do have it switched around. Showing $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$ is sufficient to show $f(n) \in \Theta(g(n))$. You can equivocally show $g(n) \in O(f(n))$.

Also, having $C = 0$ doesn't make sense unless $f(n) = 0$. You have the inequality $|f(n)| \leq C * |g(n)|$, for $n \geq k$.

Answer 2

$$[\forall n\geqslant100, f(n)\leqslant g(n)\leqslant2f(n)]\implies f(n)=\Theta(g(n))$$ In full generality, $$ f(n)=\Omega(g(n))\iff g(n)=O(f(n)) $$ $$ f(n)=\Theta(g(n))\iff[f(n)=O(g(n)),f(n)=\Omega(g(n))]$$