Proving with Big O Notations 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?
 A: 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.

A: 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)$.
A: 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$
