What is the asymptotic complexity of
$$f(n) = -\log(c^{1/n} - 1)$$
for some constant $c > 1$? I conjectured $O(\log n)$ and checking WolframAlpha does give $$\lim_{n\to\infty}\frac{f(n)}{\log(n)} = 1,$$ but I haven't found a proof yet.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
For $c \gt 1$ we have $c^{1/n} - 1 \sim \frac{1}{n}\ln c$, which gives $$\lim\limits_{n\to\infty}\frac{\log(c^{1/n} - 1)}{-\log(n)} = \lim\limits_{n\to\infty}\frac{\log\ln c - \log(n)}{-\log(n)}=1$$
For proof brought approximation we can consider limit $$\lim\limits_{x \to 0}\frac{e^x-1}{x} = \lim\limits_{x \to 0}e^x=1$$ based on L'Hôpital, Taylor expansion etc. De facto it's derivative of exponent in point $0$.
-
$\begingroup$ Could you give a reference or explanation for your approximation? $\endgroup$– orlpCommented Mar 2, 2021 at 14:10
-
$\begingroup$ Ah found it, with well-known approximation $e^x = x+ 1$ when $x \to 0 $ we have $c^{1/n} = e^{\ln(c)/n} \approx \ln(c)/n + 1$ and the rest follows. $\endgroup$– orlpCommented Mar 2, 2021 at 14:25
-