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?

I cannot comment, so I write it as an answer, which it is not. The sentence in the frame in @Adriano's answer is actually false, because the limit does not need to exist. E.g. $f(n) = (2+\sin(n))\cdot n$, $g(n) = n$. — johny bravo, Jun 22 '13 at 15:28
@johnybravo, the answer is fine, but needs some rewording. For example, there should be an absolute value sign (doesn't matter, since they are both positive), and the limit used should be the limit superior (doesn't matter, since it is the same as the limit in this case). — George V. Williams, Jun 22 '13 at 16:31

score 14 · Accepted Answer · answered May 17 '13 at 22:30

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)$.

score 4 · Answer 2 · answered May 17 '13 at 22:29

4

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

answered May 17 '13 at 22:29

DonAntonio

211,718
17
136
287

score 1 · Answer 3 · answered May 17 '13 at 23:23

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.

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

3 Answers3