I have a question about asymptotic notation in some proof of a claim which I don't fully understand. In the proof there is a part in which they show that there is a function $f:\Bbb{N} \to [0,1]$ such that $$(1-g^2(n))^n \le f(n) \le (1-g^2(n))^n e^{\frac{ng^3(n)}{2(1-g^2(n))}}$$

where $g(n) = \frac{1}{log(n)}$, and from it they conclude that $f(n) = (1-g^2(n))^{n(1-o(1))}$. What does it mean? and why is it true?


It means that $f(n)$ is equal to $(1-g^2(n))^{n(1-h(x))}$

where $h(x)$ is a function such that $\lim\limits_{g\to 0} = 0$.

This is of course the case since we have $0\leq -nh(x) \leq \log_{1-g^2(n)}(e^{\frac{ng^3(n)}{2(1-g^2(n))}})=\frac{\frac{ng^3(n)}{2(1-g^2(n))}}{\log(1-g^2(n))}=\frac{n}{2(1-1/\log(n)^2)\log(1-1/\log(n)^2)1/log(n)^ 3}$

dividing by $-n$ gives:

$0\geq h(x)\geq - \frac{1}{2(1-1/\log(n)^2)\log(1-1/\log(n)^2)1/log(n)^ 3}$.

Which implies $h(x)$ goes to zero as desired.


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.