# Asymptotic Relationship between $\frac{1}{n}$ and $\frac{1}{2^n}$

What is the asymptotic relationship between $$\frac{1}{n}$$ and $$\frac{1}{2^n}$$?

The answer here mentions that both functions are $$O(1)$$ (because they are always $$\leq 1$$) but not $$\Omega(1)$$ (because the functions will not be always greater than any constant $$c>0$$, as both are eventually 0).

Thinking of it using limits: $$\lim\limits_{n \to \infty}\frac{\tfrac{1}{n}}{\tfrac{1}{2^n}}=\infty$$, which implies that $$\frac{1}{2^n}=o(\frac{1}{n})$$. However, both functions are decreasing (not increasing) and both eventually meet at zero. I.e. no function will always be greater than the other. So I can't wrap my head around it!

I assume this question applies in general to other decreasing functions as well (e.g. $$\frac{1}{n}$$ and $$\frac{1}{n^2}$$).

• "no function will always be greater than the other": this is wrong, the functions never meet (infinity does not count). For all naturals, $\frac1n>\frac1{2^n}$.
– user16034
Oct 21, 2022 at 8:57

You are right in concluding it is $$O(1)$$ and not $$\Omega(1)$$ (talking purely about functions). However saying its $$O(1)$$ because they are always $$\leq 1$$ is slightly incorrect as it can be seen from the graph below. Since these functions are in the denominator they would approach $$0$$ very fast. In asymptotic analysis, $$n \to \infty$$ means for sufficiently large value of $$n$$, and it can be seen from the graph that even a small value$$(n=1)$$ is enough to show the asymptotic relationships between the functions.

The graph of $$\frac{1}{n}$$(green curve) approaches zero slower than that for $$\frac{1}{2^n}$$ (violet/purple curve). Clearly, $$\frac{1}{2^n}$$ is upper bounded by $$\frac{1}{n}$$ i.e. $$\frac{1}{2^n} = O(\frac{1}{n})$$ and as you yourself have mentioned in the question $$\frac{1}{2^n}=o(\frac{1}{n})$$.

Even by using the standard definition of Big-O

for $$\frac{1}{2^n} = O(\frac{1}{n})$$ we need to show

$$\frac{1}{2^n}\leq c\cdot \frac{1}{n}$$ for some positive constant $$c$$. Putting $$c=1$$ the equation holds true for all values of $$n>0$$. Similarly you can figure out the asymptotic relationships for other decreasing functions as well.

• Sorry, I didn't get what their asymptotic relationship is. Is it true that $\frac{1}{2^n} = O(\frac{1}{n})$? Oct 21, 2022 at 6:56
• Yes, I have updated my answer. Oct 21, 2022 at 7:31

Just like $$n=O(2^n)$$ (the exponential grows much much faster), $$\dfrac1n=\Omega\left(\dfrac1{2^n}\right)$$.