If $f(n) = \Theta(g(n))$, do both functions bound each other for all $n$ or only sufficiently large $n$?
If we restrict consideration to $\mathbb{N}$ and both functions are strictly positive on every $n \in \mathbb{N}$, then it is true that, if $f(n) \in \Theta(g(n))$, then there exists a $c$ such that $f(n) \leq cg(n)$ for all $n$, and vice versa.

(As pointed out in the comments, if the functions can be negative, then the answer is clearly "no", since we could take $f(1) = -1$ and $g(1) = 1$.)

The proof is straightforward. If $f(n) \in O(g(n))$, then there is an $N$ and a $C$ so that, whenever $n \geq N$, $f(n) \leq C g(n)$.

Now consider $n = 0,1,2,\dots,N-1$. For each $n$, if $g(n) &gt; f(n)$, pick some $c_n$ so that $f(n) \leq c_n g(n)$. We can easily do this because there's only $N$ of these numbers to check.

Now pick $K = \max\{C,c_0,c_1,\dots,c_{N-1}\}$. By construction, $f(n) \leq K g(n)$ for all $n$. So we're done.

The intuition here is not tricky: We know that, if we go far enough out, $C g(x)$ bounds $f(x)$. So we just check all the cases up to that point and pick the biggest bound.

If we consider strictly positive functions defined on the reals, it is not much different to prove that, if $f$ and $g$ are both continuous and bounded below by some $\delta &gt; 0$, we get the same result.