Asymptotic Problem

Question

Let us assume that $f(n)=2^{n+1}$, $g(n)=2^n$ be two functions.

Now, using limit to find $\mathcal{O}(f(n))$, $\lim_{n\to\infty} \frac{2^{n+1}}{2^n}$we get 2 as answer 2 is less than infinity, so $f(n)$ belongs to $\mathcal{O}(g(n))$.

But how is this possible as it can clearly be seen that $2^{n+1} < 2^{n}$. using limits, $f(n)$ belongs to $\mathcal{O}(g(n))$ gets proved.

Because this is the definition of big O notation! $f(n) = O(g(n))$ if $|f(n)| \le M|g(n)|$ for some constant $M$. In other words, up to a constant, $f$ and $g$ "grow at the same rate". — rogerl, Jul 24 '14 at 14:18
can you please elaborate? I know the definition of Big O, that is why i dont understand how is 2^(n+1)<2^n — girl101, Jul 24 '14 at 14:23
The Big Oh notation is about rate of growth. Both functions have the same rate of growth (an increment of $1$ in $n$ means $f$ and $g$ double). Some other funcions in $O(2^n)$ are $1000·2^n$ or $2^n + 10000$ — Darth Geek, Jul 24 '14 at 14:23
If I think I am understanding your question, the clarification is that $f = O(g)$ does not imply that $f(n) \leq g(n)$. — Jason Knapp, Jul 24 '14 at 14:27
yeah it is, 2g(n), so if both function have same rate of growth, does that mean that in such a case limit cannot be applied? — girl101, Jul 24 '14 at 14:28
The logplot of these two functions for large $n$ may provide some intuition. WolframAlpha — Semiclassical, Jul 24 '14 at 14:52

score 0 · Accepted Answer · answered Jul 24 '14 at 14:33

Wikipedia: Let $f$ and $g$ be two functions defined on some subset of the real numbers. One writes

$$f(x)=O(g(x))\text{ as }x\to\infty$$

If and only if there is a positive constant $M$ such that for all sufficiently large values of $x$, $f(x)$ is at most $M$ multiplied by the absolute value of $g(x)$. That is, $f(x)=O(g(x))$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that

$$|f(x)| \le \; M |g(x)|\text{ for all }x \ge x_0$$

As you see:

$$\lim_{n \to \infty} \frac{f(n)}{g(n)}=2$$

Then by limit definition given $\epsilon>0$ $\exists$ $n_0\in \mathbb{N}$ such:

$$\left| \frac{f(n)}{g(n)} -2 \right|<\epsilon \ \ \ \forall n\geq n_0$$

Then:

$$\left| \frac{f(n)}{g(n)}\right|\leq \left| \frac{f(n)}{g(n)} -2 \right|+2\leq \epsilon+2 \ \ \ \forall n\geq n_0 $$ Therefore:

$$\left| \frac{f(n)}{g(n)}\right|\leq \epsilon+2 \ \ \ \forall n\geq n_0$$ $$\left| f(n)\right|\leq (\epsilon+2)\left|g(n)\right| \ \ \ \forall n\geq n_0$$

Asymptotic Problem

1 Answers1