Check my proof: Big O notation

Question

I was asked the following:

We are given the functions $f(n)=n^{10\log(n)}$ and $g(n)=(\log (n))^n$.

Which of the following statements is true:

1. $f(n)\in\mathcal{O}(g(n))$,

2. $f(n) \in \mathcal{\Theta}(g(n))$,

3. $f(n) \in\mathcal{\Omega} (g(n))$

According to wolfram, the first result is true. This is because:

$$\lim_{n \to \infty} \frac{f(n)}{g(n)} =0$$ which implies $f(n)\in\mathcal{O}(g(n))$.

Here is what I did:

$f(n) = n^{10 \log(n)} = (2^{ \log (n)})^{10 \log (n)}=2^{10 (\log(n))^2}$

For $n \geq 5$, $\log (n) >2$, and so:

$2^{10 (\log(n))^2} < (\log (n))^{10 (\log(n))^2}$

notice that $$\lim_{n \to \infty} \frac{10 (\log(n))^2}{n}=0$$ (apply lhopital twice) and so if $n$ is large enough, $10 (\log(n))^2 < n$ and we can get

$$(\log (n))^{10 (\log(n))^2} < (\log(n))^{n}$$

proving the thing we wanted to prove.

My problem is that I used calculus. If possible, I would rather not use limits. I actually want to find such $n_0$ and $c$ such that $f(n) < cg(n)$ for all $n >n_0$. I did not do that in this "proof". Would appreciate help.

Answer 1

Take $c=1$, since $g$ is obviously growing way faster.

Let $n_{0}=1000000$. Now assume $n>n_{0}$. Notice the following property:

$n^{\frac{10}{n}}=(n^{\frac{1}{n}})^{10}$ is decreasing, and since plug in $n=1000$ showed that $n^{\frac{10}{n}}<2$ we have $n^{\frac{10}{n}}<2$ for all $n>n_{0}$.

Also $\log(n)>4e$ and $f(1000000)<g(1000000)$

$f(n)=n^{10\log(n)}$ so $\frac{f(n+1)}{f(n)}=\frac{(n+1)^{10\log(n+1)}}{n^{10\log(n)}}=(n+1)^{10\log(1+\frac{1}{n})}(1+\frac{1}{n})^{10\log(n)}<(n+1)^{\frac{10}{n}\log((1+\frac{1}{n})^{n})}(1+\frac{1}{n})^{n}<(n+1)^{\frac{10}{n}\log(e)}e<(2n)^{\frac{10}{n}}e<4e$.

And $\frac{g(n+1)}{g_(n)}=\frac{(\log(n+1))^{n+1}}{(\log(n))^{n}}>\frac{(\log(n))^{n+1}}{(\log(n))^{n}}=\log(n)>4e$.

Hence each step $g$ get multiplied by a larger amount than $f$ so $f$ can never catch up. Hence $c=1,n_{0}=1000000$ is a possible choice.

To prove that it's not in $\Omega$ that follow directly from the limit. If you want to go the hard way, you will have to show that no value of $c,n_{0}$ work. Once again this is just like above. The ratio $\frac{f(n)}{g(n)}$ get reduced by a factor of at least $\frac{\log(n)}{4e}>1.2$ for each step when $n>1000000$ so no value of $c$ could possibly work.

Answer 2

You might prove the following lemma and find it useful for #1:

If $f,g$ are functions taking values greater than $2$, and $\log f(x) = o(\log g(x))$, then $f(x) = o(g(x))$.

(Note that this is false in general if $o$ is replaced by $O$.)

Since $f(x) = o(g(x))$ implies $f(x) = O(g(x))$, this can help for #1 (which is a situation where taking logs makes the functions much simpler).

As for #3, note that the statement $f(x) = \Omega(g(x))$ is exactly the negation of the statement $f(x) = o(g(x))$, by definitio.