# Disproving using the definition of O

Formally show that $0.1n + 10\sqrt{n}$ is not $O(\sqrt{n})$ using the definition of $O$ only.

I cannot find much on how to solve a problem like this, nor do i know how. Am I supposed to show some contradiction by trying to prove it is $O(\sqrt{n})$? Any help on how to answer this would be appreciated.

This is about measures of complexity, so we're interested in asymptotic behavior as $n \to +\infty$, and we assume that all the functions take only non-negative values ($\forall n, f(n) \ge 0$).

• The question already tells you how to do it: use the definition of O. Do you know what the definition of O is? Then try plugging that in and see what you get. See also our reference question: cs.stackexchange.com/q/824/755. – D.W. Aug 12 '17 at 2:06

Here is one possible definition of big O (your definition might vary in details):

Let $f(n),g(n)$ be two real-valued functions such that $f(n),g(n) > 0$ for all $n$. We say that $f(n) = O(g(n))$ if there exists an integer $N$ and a real $C > 0$ such that for all $n \geq N$, $f(n) \leq Cg(n)$.

Using the rules of logic, we get a definition of the negation of big O:

Let $f(n),g(n)$ be two real-valued functions such that $f(n),g(n) > 0$ for all $n$. We say that $f(n)$ is not big $O(g(n))$ if for every integer $N$ and real $C > 0$ there exists $n \geq N$ such that $f(n) > Cg(n)$.

This is what you should prove. For each integer $N$ and real $C > 0$ you should find $n \geq N$ such that $0.1n + 10\sqrt{n} > C\sqrt{n}$.

You could use the limit definition of Big-O. Provided that the limit for both $f(x)$ and $g(x)$ exists and $g(x) \gt 0$ for all $x$, the following equivalence holds: $$f(n) \text{ is }O(g(n)) \text{ if on only if } \exists~ c\in\mathbb{R}: \lim_{n \to \infty}\frac{f(n)}{g(n)} = c, \text{ where } 0 \leq c < \infty$$ (If either limit does not exist or $g$ is not positive, then $f(n)$ may or may not be $O(g(n))$, you need to use more precise criteria to find out.)

So, if $0.1n + 10\sqrt{n}$ is $O(\sqrt{n})$ then $$\lim_{n \to \infty}\frac{0.1n + 10\sqrt{n}}{\sqrt{n}} = \lim_{n \to \infty}{0.1\sqrt{n} + 10} = \infty$$ which is not a constant.