Big O notation

From Citizendium, the Citizens' Compendium

Jump to: navigation, search

Main Article

Talk

Related Articles ^[?]

Bibliography ^[?]

External Links ^[?]

This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are subject to a disclaimer.

[edit intro]

The big O notation is a mathematical notation to express various bounds concerning asymptotic behaviour of functions. It is often used in particular applications in physics, computer science, engineering and other applied sciences. For example, a typical context use in computer science is to express the complexity of algorithms.

More formally, if f and g are real valued functions of the real variable $t$ then the notation $f(t)=O(g(t))$ indicates that there exist a real number T and a constant C such that $|f(t)|\leq C |g(t)|$ for all $t>T.$

Similarly, if $a_n$ and $b_n$ are two numerical sequences then $a_n=O(b_n)$ means that $|a_n|\le C|b_n|$ for all n big enough.

The big O notation is also often used to indicate that the absolute value of a real valued function around some neighbourhood of a point is upper bounded by a constant multiple of the absolute value of another function, in that neigbourhood. For example, for a real number $t_0$ the notation $f(t)=O(g(t-t_0))$ , where g(t) is a function which is continuous at t = 0 with g(0) = 0, denotes that there exists a real positive constant C such that $|f(t)|\leq C|g(t-t_0)|$ on some neighbourhood N of $t_0$ .