Does $n n^{1/n} =O(n)$?

Question

I was asked does $n n^{1/n} =O(n)$ ?

I can see that the left hand side is always bigger than $n$ but how would you prove the equality is false?

Answer 1

The equality is true. Recall that $\mathcal{O}(n)$ means the function is eventually $\leq C n$, where $C$ is a positive constant.

In your case, show that $n^{1/n} < e^{1/e}$ by considering the function $x^{1/x}$. We hence have for all $n \in \mathbb{N}$, $$n \cdot n^{1/n} < e^{1/e} \cdot n$$ Since, we have $n \cdot n^{1/n} < \underbrace{e^{1/e}}_{\text{const}} \cdot n$, $\forall n \in \mathbb{N}$, we have that $n \cdot n^{1/n} \in \mathcal{O}(n)$.

Answer 2

$$\frac{n\sqrt[n]n}n=\sqrt[n]n\xrightarrow[n\to\infty]{}1\implies n\sqrt[n]n=\mathcal O(n)$$

Answer 3

Alternatively, recall that:

$$f(n)=O(g(n)) \iff \lim_{n\to\infty}{\frac{f(n)}{g(n)}} = C \text{ , for some constant } C\ge0$$

Thus, to see why $nn^{1/n} = O(n)$, it suffices to notice that:

$$ \lim_{n\to\infty}{\frac{nn^{1/n}}{n}} = \lim_{n\to\infty}{n^{1/n}} = \lim_{n\to\infty}{e^{\ln{(n^{1/n})}}} = e^{\lim_{n\to\infty}{(\ln{n})/n}} = e^{\lim_{n\to\infty}{(1/n)/1}} = e^{0} = 1 \ge 0 $$

by using L'Hopital's rule.