patternMinor
Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$
Viewed 0 times
fracasymptoticslog
Problem
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)$?
\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)$?
Solution
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)$.
$$
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)$.
Context
StackExchange Computer Science Q#117220, answer score: 5
Revisions (0)
No revisions yet.