Big O Notation
A mathematical notation classifying algorithms according to how their execution time or memory requirements grow as input size N increases.
Governing formula
f(N) = O(g(N)) if |f(N)| ≤ C |g(N)| for N ≥ N₀
SI unit
Algorithmic Asymptotic Complexity
In depth
Quantifies computational efficiency. For example, direct N-body gravitational force calculation is O(N²), whereas the Barnes-Hut octree algorithm reduces complexity to O(N log N).
Examples in the real world
Comparing O(N²) direct Fourier Transform against O(N log N) Fast Fourier Transform (FFT) computational scaling.