2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you means by "find"? Because using limit already means you already find it (since one must exist, so just take anything just a bit above the infimum). $\endgroup$ – Gina Jul 27 '14 at 19:21
  • $\begingroup$ By find I mean give a natural number $n_0$ and real number $c$ such that $f(n) < cg(n)$ for all $n > n_0$. I did not find such numbers. I merely said they exist. I want to actually be able to say what they are. Give an example. $\endgroup$ – Oria Gruber Jul 27 '14 at 19:36
  • $\begingroup$ And another thing, how can we show that $f$ is not $\Omega (g)$? How do you prove that something is not Omega $\endgroup$ – Oria Gruber Jul 27 '14 at 19:45
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.