Can $\Theta(f_1) = \Theta(f_2)$?

Question

Does $\Theta(n^3+2n+1) = \Theta(n^3)$ hold? I'm so used to proving that a concrete function is Big-Whatever of another function, but never that Big-Whatever of a function is Big-Whatever of another function.

Answer 1

Hint: If $\lim_{n \to \infty} f(n)/g(n) = c$ where $c$ is a positive constant not zero, then $f(n) = \Theta(g(n))$ and $g(n) = \Theta(f(n))$.

Answer 2

The problem is that $f=\Theta(g)$ is bad notation, because the two sides aren't "equal" in the obvious sense. One way to make the notation precise is to think of $\Theta(g)$ as the collection of all functions which "are big-theta of $g$." In other words, $\Theta(g)$ consists of all the functions $f$ so that $$c\cdot g(n)\le f(n)\le C\cdot g(n)$$ for some constants $c$ and $C$, so long as $n$ is large enough. Now the notation $$f\in\Theta(g)$$ makes perfect sense. It means that $f$ is a function belonging to the collection of functions which are big-theta of $g$.

I mention all of this, because with this interpretation, one can make sense of $\Theta(f)=\Theta(g)$. It is saying that two sets are equal. The way to prove that two sets are equal is to show that one contains the other, and vice-versa. So you would need to show that if a function is big-theta of $f$ then it is big-theta of $g$, and vice-versa.

In your example, a proof would look like this:

Suppose $f\in\Theta(n^3)$. Then there are constants $c$ and $C$ such that $cn^3\le f(n)\le Cn^3$ for large enough $n$. Note that $n^3\le n^3+2n+1$, and $n^3+2n+1\le 2n^3$ for $n$ large enough. Putting these inequalities together yields $$\frac{c}{2}(n^3+2n+1)\le f(n)\le C\cdot(n^3+2n+1),$$ which means $f\in\Theta(n^3+2n+1)$. Thus, any function in $\Theta(n^3)$ is also in $\Theta(n^3+2n+1)$, meaning that $\Theta(n^3)\subseteq\Theta(n^3+2n+1)$. A similar argument proves the reverse containment, from which we deduce that $\Theta(n^3)=\Theta(n^3+2n+1)$.