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?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ First of all, although we often write $f(z)=O(g(z))$, we hardly ever write $O(g(z))=f(z)$. That's because the relationship is really not equality, but a matching rule (or membership.) So you want that $10^n$ is not $O(3^{2n})$. $\endgroup$– Thomas AndrewsJan 21, 2015 at 23:27
-
$\begingroup$ What kind of number is $n$ supposed to be? If $n$ is not meant to be a complex number, you may want to remove the complex-analysis tag, or explain what the tag is referring to. $\endgroup$– VectornautJan 21, 2015 at 23:28
-
$\begingroup$ Sorry Vectornaut, the complex-analysis tag was a mistake, I wanted to add a complexity tag but I guess new users like myself can't make new tags. Also, I'm still very new to this type of math, so despite everyone's efforts at helping me, I'm still very much in the dark. $\endgroup$– GeorgeJan 21, 2015 at 23:41
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
3
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)$.
-
1$\begingroup$ Are you sure you want a limit there, rather than a limit superior? In Wikipedia's definition, you can have $f \in O(g)$ even if the limit $\lim_{x \to \infty} f(x)/g(x)$ doesn't exist. $\endgroup$ Jan 21, 2015 at 23:46
-
$\begingroup$ @Vectornaut I believe you are correct. (It seems we're not the first to have this discussion about this approach.) I'll edit after I eat. (To confirm, since I'm not 100% familiar with limit superior as opposed to a "normal" limit: I believe my manipulations are valid even with $\lim\sup$ instead of $\lim$, right?) $\endgroup$– apnortonJan 22, 2015 at 0:00
-
$\begingroup$ Except for the last line, where you give the value of the limit, your manipulations don't actually depend on the definition of the limit superior at all—you're just rewriting the expression for the function you're taking the limit of. $\endgroup$ Jan 22, 2015 at 0:28
$\begingroup$
$\endgroup$
6
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$
-
$\begingroup$ I think I'm starting to understand, thanks! But are you sure that $O(10^n)$ is the same as just $10^n$? $\endgroup$– GeorgeJan 21, 2015 at 23:54
-
$\begingroup$ @George No, $O(10^n)$ is certainly not the same as just $10^n$. The Big-Oh notation is a really big mess. My opinion is that it is best to consider $O(10^n)$ as a collection of functions, and use $f \in O(g)$ instead of $f = O(g)$. A set of functions $O(10^n)$ is not the same as just a single function $10^n$. $\endgroup$– dtldarekJan 22, 2015 at 0:00
-
$\begingroup$ Okay, I was confused because you were comparing $O(10^n)$ with $O(3^{2n})$, though I'm just trying to prove $10^n =/= O(3^{2n})$, I'm sorry for my ignorance on the topic $\endgroup$– GeorgeJan 22, 2015 at 0:05
-
$\begingroup$ @George Ok, which do you want: $10^n \neq O(3^{2n})$ or $O(10^n) \neq O(3^{2n})$? The former is a messy notation, which would be better understood as $10^n \notin O(3^{2n})$, while the latter is an inequality on sets (i.e. we need to show a member of one that is not a member of the other). $\endgroup$– dtldarekJan 22, 2015 at 0:08
-
$\begingroup$ The former is what I'm looking for. The exact question from the book, if it helps, is "Use a proof by contradiction to show that $10^n$ is not $O(3^{2n})$." $\endgroup$– GeorgeJan 22, 2015 at 0:11