# Why is (small) $o(n^2) \neq n^2$? [duplicate]

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

• $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. – mdxn Mar 26 '16 at 19:05
• 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. – David Richerby Mar 26 '16 at 19:22
• If $n^2=o(n^2)$, then $\lim\limits_{n\to\infty}\dfrac{n^2}{n^2}=0$. – Ribz Mar 26 '16 at 20:19
• @mdxn "but the = is dropped" Yes but look at my answer, there's an additional constraint concerning the coefficient in the definition. – Auberon Mar 26 '16 at 20:58
• @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. – David Richerby Mar 26 '16 at 22:01

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.