A function that

asymptotically describes growth rate,

notably in Big O notation:

\(\mathcal{O}(1)\)

constant

\(\mathcal{O}(\log n)\)

logarithmic

\(\mathcal{O}(n)\)

linear

\(\mathcal{O}(n \log n)\)

log-linear

\(\mathcal{O}(n^2)\)

quadratic

\(\mathcal{O}(n^3)\)

cubic

\(\mathcal{O}(n^c)\)

polynomial

\(\mathcal{O}(c^n)\)

exponential

\(\mathcal{O}(n!)\)

factorial

where

• \(n\) is the input size
• \(c\) is a constant.