= Solution
For real-valued <functions>, use magnitude comparisons. The constants below are independent of $n$.
The statement $f(n)=O(g(n))$ in <Big O notation> means that some $C>0$ and <integer> $N$ satisfy $|f(n)|\leq C|g(n)|$ for all $n\geq N$. The statement $f(n)=\Omega(g(n))$ in <big omega notation> means that some $c>0$ and $N$ satisfy $|f(n)|\geq c|g(n)|$ for all $n\geq N$.
Finally, $f(n)=\Theta(g(n))$ in <big theta notation> means that some $c,C>0$ and $N$ satisfy
$$
\boxed{c|g(n)|\leq|f(n)|\leq C|g(n)|\qquad(n\geq N).}
$$
Equivalently it is both an eventual <upper bound> and an eventual <lower bound>. These definitions ignore a finite initial segment; they do not assert pointwise inequalities with constant one.
Back to article page
