# Definition: Big O Notation

Let $$g,f:\mathbb N\mapsto\mathbb R$$ be two functions of natural numbers to real numbers. We say that $$f$$ has order of $$g$$ and write $f=\mathcal O(g),\quad\quad( * )$ if and only if there is a positive constant $$c\in\mathbb R_+$$ such that for all sufficiently large $$n\in\mathbb N$$, i.e. all $$n \ge N( c )$$1 the absolute values of both functions fulfill the following relation:

$|f(n)|\le c|g(n)|$

Note: The use of "$$=$$" in $$( * )$$ is somewhat different from a usual equation. This notation does not mean that $$f$$ "equals" $$\mathcal O(g)$$. It rather means that, while $$f$$ is a function, $$\mathcal O(g)$$ is a whole class of functions $$g$$ such that for each such $$g$$ there exists constants $$c$$ and $$N(c)$$ such that $$|f(n)|\le c|g(n)|$$ for all $$n\ge N( c )$$.

Proofs: 1
Propositions: 2

Github: ### References

#### Bibliography

1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition

#### Footnotes

1. The number $$N( c )$$ depends on the constant $$c$$.