Proving with Big O Notations

Question

Is there a way I can prove that $O(3^{2n})$ does NOT equal $10^n$? How would that be done? Also, is it okay to simplify $O(3^{2n})$ to $O(9^n)$ to do so?

Answer 1

In this answer, whenever I say "function," I mean a positive real-valued function on the natural numbers $\{1, 2, 3, \ldots\}$.

Big-O notation is a way to compare the growth rates of functions as their arguments go to infinity. Let's define a relation $\preccurlyeq$ between functions by saying that $f \preccurlyeq g$ if the ratio $\frac{f(n)}{g(n)}$ remains bounded below some constant as $n$ goes to infinity.

The symbol $O(g)$ refers to the set of functions $f$ with the property that $f \preccurlyeq g$. When talking quickly, people often say things like "$f$ is $O(g)$." They really mean "$f$ is in the set $O(g)$," which is the same thing as saying "$f \preccurlyeq g$."

Here are some examples of how the $\preccurlyeq$ relation works.

• The statement $5n^2 + 10 \preccurlyeq n^3$ is true, because $\frac{5 n^2 + 10}{n^3}$ is always less or equal to than 15, no matter how big $n$ gets. You can see this by rewriting the ratio as $5 \frac{1}{n} + 10 \frac{1}{n^3}$.

• The statement $n^3 \preccurlyeq n^2$ is false, because you can make $\frac{n^3}{n^2}$ as big as you want by setting $n$ high enough. You can see this by rewriting the ratio as $n$.

• The statement $n^3 \preccurlyeq n^3 + 1$ is true, because $\frac{n^3}{n^3 + 1}$ is always less than 1, no matter how big $n$ gets.

• The statement $n^3 + 1 \preccurlyeq n^3$ is also true, because $\frac{n^3 + 1}{n^3}$ is always less than or equal to 2, no matter how big $n$ gets.

• The statement $9^n \preccurlyeq 10^n$ is true, because $\frac{9^n}{10^n}$ is always less than 1, no matter how large $n$ gets. You can see this by rewriting the ratio as $\left(\frac{9}{10}\right)^n$.

• The statement $10^n \preccurlyeq 9^n$ is false, because you can make $\frac{10^n}{9^n}$ as large as you want by setting $n$ high enough. You can see this by rewriting the ratio as $\left(\frac{10}{9}\right)^n$.

---

The $\preccurlyeq$ relation between functions acts like the familiar $\le$ relation between numbers in two important ways:

• It's transitive: if $f \preccurlyeq g$ and $g \preccurlyeq h$, then $f \preccurlyeq h$.
• It's reflexive: $f \preccurlyeq f$ for any function $f$.

A relation with these properties is called a preorder. Keeping this properties in mind is very helpful when you're trying to prove things about the $\preccurlyeq$ relation. Here's an example.

Let's say we want to prove that $5n^2 + 10 \preccurlyeq n^3 + 1$. We know from before that $5n^2 + 10 \preccurlyeq n^3$, and that $n^3 \preccurlyeq n^3 + 1$. Because $\preccurlyeq$ is trasitive, these two facts together imply the one we want to prove.

Answer 2

To answer your second question first: yes, it is allowable to simplify $3^{2n}$ to $9^n$.

Recall that $f\in \mathcal O(g)$ iff: $$\limsup_{x\to\infty}\frac{f(x)}{g(x)} = c,\quad 0\leq c < \infty$$

Letting $f(x) = 10^x$ and $g(x) = 9^x$, and taking the limit: \begin{align} \limsup_{x\to\infty}\frac{f(x)}{g(x)} &= \limsup_{x\to\infty}\frac{10^x}{9^x}\\ &= \limsup_{x\to\infty}\left(\frac{10}{9}\right)^x \\ &\to \infty \end{align}

(The last simplification is because $10/9 > 1$.)

Therefore, $f\not\in\mathcal O(g)$.

Answer 3

It seems that you want to show that $10^n\notin O(3^{2n})$.

To prove that $10^n$ is not $O(3^{2n})$ it is enough to show that for any $M$ there is $n$ such that $10^n > M\cdot3^{2n}$, in particular

\begin{align} 10^n &> M\cdot 9^n\\ \frac{10^n}{9^n} &> M \\ n &> \log_{\frac{10}{9}} M \end{align}

so $n = \left\lfloor\frac{\log M}{\log\frac{10}{9}}\right\rfloor + 1$ suffices.

I hope this helps $\ddot\smile$