# Proving if a function is an upper bound

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.

Just looking at the plot we can easily see, that these two complexities are completely different. 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.

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