patternMinor
Asymptotic complexity of $-\log(c^{1/n} - 1)$
Viewed 0 times
asymptoticcomplexitylog
Problem
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.
$$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.
Solution
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$.
$$\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$.
Context
StackExchange Computer Science Q#136095, answer score: 3
Revisions (0)
No revisions yet.