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


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$ – narek Bojikian Nov 17 '19 at 16:00
  • $\begingroup$ @narekBojikian I didn't get your idea. My analysis is also base on the large values of $n$. $\endgroup$ – OmG Nov 17 '19 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$ – Ryan Nov 17 '19 at 17:23
  • $\begingroup$ Oh sorry my fault. I get it now. $\endgroup$ – narek Bojikian Nov 17 '19 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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