Skip to content

Orders of growth

Level UniversityDifficulty ★★★★★Concept⌖ Open in the map

What is it?

The hierarchy of how fast functions grow: logarithms ≪ powers ≪ exponentials ≪ factorials. It is the language in which we compare algorithms.

Formulas

$\log n \ll n^{\varepsilon} \ll n^k \ll a^n \ll n! \ll n^n \qquad (\varepsilon > 0,\ a > 1)$; $n! \sim \sqrt{2\pi n}\,\left(\frac{n}{e}\right)^n$
Stirling's formula

Where it shows up in computing

Algorithm analysis and complexity★★★★★fundamentalScientific computing and algorithms
Choosing between an $O(n^2)$ and an $O(n \log n)$ algorithm is a comparison of orders of growth.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

λ Scientific computing and algorithms

Algorithm analysis and complexity★★★★★
Asymptotic notation (O, o, Ω, Θ)→Order of convergence→Scientific computing★★★★★
Asymptotic notation (O, o, Ω, Θ)→Monte Carlo methods★★★★★

ℒ AI and machine learning

Asymptotic notation (O, o, Ω, Θ)→Order of convergence→Gradient descent★★★★★
Asymptotic notation (O, o, Ω, Θ)→Order of convergence→Gradient descent→Learning rate★★★★★
Asymptotic notation (O, o, Ω, Θ)→Order of convergence→Gradient descent→Backpropagation★★★★★
Asymptotic notation (O, o, Ω, Θ)→Order of convergence→Gradient descent→Stochastic gradient descent (SGD)★★★★★
Asymptotic notation (O, o, Ω, Θ)→Order of convergence→Gradient descent→Loss landscape★★★★★
Asymptotic notation (O, o, Ω, Θ)→Order of convergence→Gradient descent→Reinforcement learning★★★★★
+3

3D Computer graphics

Asymptotic notation (O, o, Ω, Θ)→Monte Carlo methods→The rendering equation★★★★★

⇄ Optimization and systems

Asymptotic notation (O, o, Ω, Θ)→Order of convergence→Gradient descent→Recommender systems★★★★★

What depends on it

Asymptotic notation (O, o, Ω, Θ)

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.