Big O notation

Big O notation is a mathematical notation that describes the approximate size of a function on a domain. Big O is a member of a family of notations invented by the German mathematicians Paul Bachmann and Edmund Landau and expanded by others, collectively called Bachmann–Landau notation. The letter O stands for Ordnung, that is, the order of approximation. In computer science, big O notation is used to classify algorithms by how their run time or space requirements grow with the input. In analytic number theory, big O notation expresses bounds on the growth of an arithmetical function, as for the remainder term in the prime number theorem. In mathematical analysis, including calculus, Big O notation bounds the error when truncating a power series and expresses the quality of approximation of a real or complex valued function by a simpler function. Often, big O notation characterizes functions according to their growth rates as the variable becomes large: different functions with the same asymptotic growth rate may be represented using the same O notation. The letter O is used because the growth rate of a function is also referred to as the order of the function. A description of a function in terms of big O notation only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o {\displaystyle o} , ∼ {\displaystyle \sim } , Ω {\displaystyle \Omega } , ≪ {\displaystyle \ll } , ≫ {\displaystyle \gg } , ≍ {\displaystyle \asymp } , ω {\displaystyle \omega } , and Θ {\displaystyle \Theta } to describe other kinds of bounds on growth rates. Bachmann proposed the notation in 1894 and Landau extended it in 1909. An earlier notation was proposed by Paul du Bois-Reymond in 1870.