2
$\begingroup$

This question already has an answer here:

We know that $10n^2 = O(n^2)$ but $10n^2 \neq o(n^2)$. What is the underlying principle?

$\endgroup$

marked as duplicate by David Richerby, Ran G., Luke Mathieson, Gilles 'SO- stop being evil' Apr 4 '16 at 23:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ $f(n) = o(g(n))$ means that $f(n)$ is strictly asymptotically bounded above by $g(n)$ as $n \rightarrow \inf$. It's similar to big $O$, but the $=$ is dropped. $\endgroup$ – mdxn Mar 26 '16 at 19:05
  • 3
    $\begingroup$ The underlying principle is that the definition of $O(\cdot)$ and the definition of $o(\cdot)$ are different. Did you read the definitions? They are repeated in hundreds of textbooks and websites. $\endgroup$ – David Richerby Mar 26 '16 at 19:22
  • $\begingroup$ If $n^2=o(n^2)$, then $\lim\limits_{n\to\infty}\dfrac{n^2}{n^2}=0$. $\endgroup$ – Ribz Mar 26 '16 at 20:19
  • $\begingroup$ @mdxn "but the = is dropped" Yes but look at my answer, there's an additional constraint concerning the coefficient in the definition. $\endgroup$ – Auberon Mar 26 '16 at 20:58
  • 1
    $\begingroup$ @Auberon '"but the = is dropped" Yes' Actually, no. As your answer shows, it's not just that we change from $f(n)\leq c\,g(n)$ to $f(n)<c\,g(n)$: the significant point is that the quantification on $c$ changes. $\endgroup$ – David Richerby Mar 26 '16 at 22:01
6
$\begingroup$

The underlying principle is that the definitions of small o and big O are different.

Big O definition

$O(f(n)) = \{g(n) | \exists c > 0, \exists n_0 > 0, \forall n > n_0 : 0 \leq g(n) \leq c*f(n)\}$

In words:

$g(n)$ is an element of $O(f(n))$ if there exists a $c > 0$ and a $n_0 > 0$ such that for all $n > n_0$, $0 \leq g(n) \leq c*g(n)$

In your example $f(n) = n^2$ and $g(n) = 10n^2$

If we pick $c = 20$, $n_0 = 1$, you can check that for all $n > 1$, $0 \leq 10n^2 \leq 20*n^2$, so $10n^2 \in O(n^2)$

Small O definition

$o(f(n)) = \{g(n) | \forall c > 0, \exists n_0 > 0, \forall n > n_0 : 0 \leq g(n) < c*f(n)\}$

In words:

$g(n)$ is an element of $o(f(n))$ if for any $c > 0$, there exists a $n_0 > 0$ so that for all $n > n_0$, $0 \leq g(n) < c*f(n)$.

In your example $f(n) = n^2$ and $g(n) = 10n^2$

If we pick $c = 1$, you can check that there is no $n_0 > 0$ so that for all $n > n_0$, $0 \leq 10n^2 < 1*n^2$

Therefore the condition does not hold and $10n^2 \notin o(n^2)$.

Informal explanation

$g(n) \in O(f(n))$ if $g(n)$ grows slower than or in the same fashion as $f(n)$. $g(n) = 10n^2$ grows in the same fashion (quadratically) as $f(n) = n^2$, so $10n^2 \in O(n^2)$.

$g(n) \in o(f(n))$ if $g(n)$ grows strictly slower than $f(n)$. $g(n) = 10n^2$ grows in the same fashion and thus not strictly slower than $f(n) = n^2$, so $10n^2 \notin o(n^2)$

NOTE: I've used notation like $10n^2 \in O(n^2)$ because the definitions were actually sets. But in practice, there's accepted notation abuse and $10n^2 = O(n^2)$ is written instead.

$\endgroup$

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