1
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.