This is a family of notations related to the <big O notation>. A good mnemonic summary of all notations would be:
* <big O notation>: $|f| \le g$
* <little-o notation>: $|f| \lt g$


Big O notation family

A good definition is that the <sparse matrix> has non-zero entries proportional the number of rows. Therefore this is <Big O notation> less than something that has $N^2$ non zero entries. Of course, this only makes sense when generalizing to larger and larger matrices, otherwise we could take the constant of proportionality very high for one specific matrix.

Of course, this only makes sense when generalizing to larger and larger matrices, otherwise we could take the constant of proportionality very high for one specific matrix.


Dense and sparse matrices

{title2=$o(n)$}

Stronger version of the <big O notation>, basically means that ratio goes to zero. In <big O notation>, the ratio does not need to go to zero.

So in informal terms, <big O notation> means $\leq$, and <little-o notation> means $<$.

E.g.:
* $x = O(x)$
* $x \ne o(x)$K does not tend to zero
* $x = O(x^2)$
* $x = o(x^2)$


Little-o notation

{title2=$O(n)$}
{wiki}

Module bound above, possibly multiplied by a constant:
$$
f(x) = O(g(x))
$$
is defined as:
$$
\exists M > 0 \exists x_0  \forall x > x_0 \colon |f(x)| \leq M g(x)
$$

E.g.:
* $\forall c \in \R x + c = O(x)$. For $c < 0$, $M = 1$ is enough. Otherwise, any $M > 1$ will do, the bottom line will always catch up to the top one eventually.


Ciro Santilli @cirosantilli 37

 Incoming links: Big O notation