How do I show $\sqrt{n} \not \in O(\log{n})$? 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.
 A: 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.
A: 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.
