How do I show $\sqrt{n} \not \in O(\log{n})$?

Question

I'm trying to derive a contradiction. So I suppose $\sqrt{n} \in O(\log{n})$. Then there exist $c, N$ such that $\sqrt{n} \leq c\log{n}$ for all $n > N$. I tried transforming this to the integral representation, i.e.

$$ \frac{1}{2} \int_0^n \frac{1}{\sqrt{x}} dx < c \int_1^n \frac{1}{x} dx \quad \forall n > N$$

But I'm unsure of how to get rid of the constant $c$ and derive an explicit contradiction from here.

Answer 1

You can try using L'Hopital's rule:

first, note that

$$\lim_{n\to \infty}\frac{\sqrt{n}}{\log n}=\lim_{n\to \infty} \frac{1}{2} \frac{1/\sqrt{n}}{1/n} =\lim_{n\to \infty}\frac{1}{2} \sqrt{n}=\infty.$$

So, for any $c$, there exists $n$ sufficiently large so that

$$\frac{\sqrt{n}}{\log n} > c.$$

This provides the desired contradiction.

Answer 2

I think the integral representation is overkill here (unless you're doing this to get practice with that representation).

If you're okay with a slightly more off-the-cuff proof: consider defining $k = \frac{1}{2}\log n$, for $n\in \mathbb{R}_+$. Now, you can calculate $$\begin{align}\sqrt{\vphantom{I}n} &= e^k & c\log n &= 2ck\end{align}$$ Express the condition you want to disprove in terms of $k$ and you get $$e^k \leq 2ck$$ It shouldn't be hard to show that this is false for all $k$ above some value. I leave that to you.

If, however, you do want to practice the integral representation, you can split the left-hand integral as follows: $$\frac{1}{2}\int_0^1\frac{1}{\sqrt{x}}dx + \frac{1}{2}\int_1^n \frac{1}{\sqrt{x}}dx < c\int_1^n\frac{1}{x}dx$$ Then you can combine the two integrals over $[1,n]$ $$\frac{1}{2}\int_0^1\frac{1}{\sqrt{x}}dx < c\int_1^n\biggl(\frac{1}{x} - \frac{1}{\sqrt{x}}\biggr)dx$$ Consider whether the quantity on the left is positive, and also whether the quantity on the right is positive. Remember that the integral of a function over a positively-oriented domain, if the function is positive (or negative) over the entire domain, is positive (or negative respectively). Then consider what happens to the quantity on the right as $n$ becomes larger.