0
$\begingroup$

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}$).

$\endgroup$
1
  • $\begingroup$ "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}$. $\endgroup$
    – user16034
    Oct 21, 2022 at 8:57

2 Answers 2

1
$\begingroup$

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.

asymptotics of functions

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.