MathLiveBig O notation
Big O notation states that f grows no faster than g up to a constant factor, for arguments large enough. It is used to describe upper bounds on asymptotic growth, especially for algorithm running times.
f(x) = O(g(x)) \text{ as } x \rightarrow \infty \iff \exists M>0, \; x_0 \in \mathbb{R} : |f(x)| \leq M\, g(x) \quad \forall x \geq x_0What the symbols mean
| the function being bounded | |
| the comparison function | |
| a positive constant bounding the ratio | |
| a threshold beyond which the bound holds | |
| the variable tending to infinity |
About this formula
- FieldMathematics
- TopicAsymptotic analysis
- LevelUniversity
- Also calledLandau notation, Bachmann-Landau notation, asymptotic notation, Landau symbol, order of growth upper bound, O notation definition
- SourceWikidata Q269878
Write it in Obsidian
MathLive is a free visual math editor for Obsidian. Run Find a formula, type “big o notation”, and it goes into your note as editable LaTeX. You can also scan formulas from screenshots, PDFs and handwriting.