1
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – D.W. Aug 12 '17 at 2:06
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

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