Let $f(n) = (\log n)^n$ and $g(n) = n^2$

By taking a large value, I could make out that $f(n) > g(n)$ .

I want to know if $f(n) \in \Theta(n^2)$ . For proving this, I need to find out the value of $c$ such that $f(n) \le c \cdot g(n)$ .

How do I find the value of $c$ ? By seeing the function it seems like no $c$ exists. But I am not able to prove or disprove it.

Please help.


Just looking at the plot we can easily see, that these two complexities are completely different.

Plot log log n vs n^2

To prove it, we have to show that there doesn't exist a $c \in \mathbb{R}$ such that

$$(\log n)^n \le c \cdot n^2$$

We can take the $\log$ $$n\cdot \log\log n \le \log c + 2\log n$$ Because $3 \le \log\log n$ and $\log n \le n$ for big $n$, also the following inequalities have to hold:

$$3n \le n\cdot \log\log n \le \log c + 2\log n \le \log c + 2n$$

And therefore also the following inequaltiy has to hold:

$$3n \le \log c + 2n$$

This implies $n \le \log c$ or $e^n \le c$. And there is no $c \in \mathbb{R}^+$ with $c \ge e^n$ for all $n$

The proof is probably way too complicated, but it was the first thing that came to my mind.

  • $\begingroup$ For $n$ large enough, $\log n\ge 2$, so $(\log n)^n\ge 2^n = \omega(n^2)$. $\endgroup$ – Louis Aug 15 '17 at 8:57

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.