Asymptotic Notation

AnalysisAlgorithmsProbabilityTheory

Big O Notation

We write: as if such that Alternatively, if such that for Big O notation indicates that f grows no faster than g (but possibly as fast as)

Little O Notation

We write that as if such that

Alternatively, if such that for Little O notation indicates that f grows strictly slower than g

Asymptotic Equivalence

We write that as if such that Or equivalently:

Example (Stirling’s approximation):