I am trying to understand the asymptotics of
\begin{equation} f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})} \end{equation} In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
From this post, you can approximate $\log(1+x)$ with $x$ for little values of $x$. Hence,
$$ f(n) \sim \frac{1}{\frac{1}{2^n-1}} = 2^n-1 $$
Therefore, you can't find any constant $c$, such that $f(n) = O(n^c)$, as it is $\Theta(2^n)$.
-
$\begingroup$ I doubt this result since we are only interested in very large values of n (greater than some $n_0$). I even think the expression is true for reasonably small values of $c$ (close to 1). $\endgroup$ Commented Nov 17, 2019 at 16:00
-
$\begingroup$ @narekBojikian I didn't get your idea. My analysis is also base on the large values of $n$. $\endgroup$– OmGCommented Nov 17, 2019 at 16:04
-
4$\begingroup$ I think that the answer is correct. As $n\rightarrow \infty$, $\frac{1}{2^n -1} \rightarrow 0$ - i.e. for large values of $n$ it is indeed true that $\log(1 + \frac{1}{2^n-1}) \simeq \frac{1}{2^n-1} $. $\endgroup$– RyanCommented Nov 17, 2019 at 17:23
-
$\begingroup$ Oh sorry my fault. I get it now. $\endgroup$ Commented Nov 17, 2019 at 21:38