How to prove big O notation

Question

How can I prove that $f_1(n) = n^{0.999999} \cdot \log_2n$ is $O(f_2(n))$ where $f_2(n) = 1.000001^n$? I'm trying to understand how to prove when a function is O of another one, but I don't get what I'm supposed to do.

Answer 1

You have to show that $\dfrac{f_1(n)}{f_2(n)}$is bounded when $n\to\infty$.

Doing some elementary asymptotic analysis, you know that $\log_2(n)=o\bigl(n^{0.000\,001}\bigr)$, so $$f_2(n)=n^{0.999\,999} \cdot \log_2n=n^{0.999\,999} \cdot o\bigl(n^{0.000\,001}\bigr) = o\bigl(n^{0.999\,999} \cdot n^{0.000\,001}\bigr)=o(n).$$

Now, for any $a>1$, you have $n=o\bigl(a^n)$. Therefor, one concludes a stronger assertion: $\:f_1(n)=o\bigl(f_2(n)\bigr). $

Answer 2

You should do estimations:

Firstly, we know, that $ \log _{2} n < n $, $ \forall n\in\mathbb{N}$. So $f_1(n) = n^{0.999999} \cdot \log_2n < n^{1.999999}$.

Then, is known, that for $ \forall k > 1 $ and $a>1$ there $\exists N \in \mathbb{N}$ such, that for $\forall n>N$ is true $n^{k}<a^{n} $. In mathematical analysis books, usually, this is proved using binomial formula .

In your case $a=1.000001$. So we have

$\exists N \in \mathbb{N}$ such, that for $\forall n>N$ we have $f_1(n) < 1.000001^{n} = f_2(n)$.

This gives us exact definition for big-O, using constant $C=1$.