-2
$\begingroup$

This question already has an answer here:

I need help with a home task with computer science. the problem is: compare the two complexity functions: $F(n) = n^{10\log n}$ and $G(n) = (\log n)^n$. Which is $O(\ )$ of the other? Which is $\Omega(\ )$ of the other?

$\endgroup$

marked as duplicate by David Richerby, Gilles 'SO- stop being evil' Mar 11 '16 at 21:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

$F(n) = n^{10\log{n}}$ and $G(n) = (\log{n})^n$

The crux of the solution is to take $\log$ on both sides of both functions to get $$F'(n) = \log{F(n)} = 10\log^2{n}$$ $$G'(n) = \log{G(n)} = n\log\log{n}$$ $$\exists c,N \, s.t. \ \log^2n \le c*n\log\log n \ \ \forall n > N$$

I'll leave the proof of the above statement to you as an exercise. Thus we can now conclude that

$$\implies F'(n) = \mathcal{O}(G'(n))$$ $$\implies e^{F'(n)} = \mathcal{O}(e^{G'(n)}) $$ $$\implies F(n) = \mathcal{O}(G(n))$$

This is due to the fact that $\log(x)$ is a monotonically increasing function. This should be sufficient for you to proceed further for $\Omega$.

$\endgroup$
  • $\begingroup$ can you show me your proof for that? I don't really like my solution using lapital... can you help me? $\endgroup$ – Itamar Silverstein Mar 15 '16 at 17:13
  • $\begingroup$ @ItamarSilverstein proof for which part? $\endgroup$ – Banach Tarski Mar 15 '16 at 17:14
  • $\begingroup$ for log(n)*log(n)<= c * n*log(log(n)) $\endgroup$ – Itamar Silverstein Mar 15 '16 at 17:20
  • $\begingroup$ At $n = 2, \log^2{n} = 1$ and $n = 2$. Now observe differentiate both functions and observe the rate of growth of both functions. For $f(n) = n, f'(n) = 1$ and for $g(n) = \log^2{n}, g'(n) = \frac{2\log n}{n}$ $g'(n) \le f'(n) \ \forall n > 2$ Integrating on both sides we obtain $g(n) \le f(n) + c \implies \log^{n} \in \mathcal{O}(n) \implies \log^{n} \in \mathcal{O}{(n\log\log{n})}$ $\endgroup$ – Banach Tarski Mar 15 '16 at 17:48
  • $\begingroup$ but the function is not f(n) = n. it is f(n) = log(n)*log(n), and g(n) is n*log(log(n)). $\endgroup$ – Itamar Silverstein Mar 15 '16 at 17:58
1
$\begingroup$

[Note: this probably should be a comment, but it's too long and I don't like comments that need to be split over multiple entries.]

You need to be a bit careful with these arguments, since it's not always the case that $$\log f(n)\in O(\log g(n))\Longrightarrow f(n)\in O(g(n))$$ Consider, for example, $f(n)=3^n, g(n)=2^n$. We obviously have $\log 3^n\in O(\log 2^n)$, since $n\log3\in O(n\log 2)$, but we can't conclude from that that $3^n\in O(2^n)$.

See here for a further discussion. By the way, in this particular case, Banach Tarski's answer was correct.

$\endgroup$
0
$\begingroup$

You can also solve this problem by rewriting $n^{10 \log(n)} = e^{10 \log^2(n)}$.

Now, in $(\log(n))^n$, both the base and the exponent grow asymptotically faster.

This is not completely rigorous, but can at least help to give the idea for which function is the $O$ of which function.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.