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.

Answer 1

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$$