Big-O notation is a mathematical concept commonly utilized to describe the limiting behaviour of functions with very large inputs. Formally, it can be defined as follows:

is said to be in if there exist a real number and a natural number such that , for all .

Alternatively, .

Example

Variants

Big Omega Notation

Big omega notation written as can effectively be thought of as the inverse of big-O notation as it is usually defined as .

Alternatively, it can be defined independently from Big-O notation as follows

is said to be in if there exist a real number and a natural number such that , for all .

Alternatively, .

Example

Big Theta Notation

Big theta notation written as is a method for describing both the upper and lower limits of a function, and is usually defined as .

Alternatively, it can be defined independently from Big-O notation as follows

is said to be in if there exist two a real numbers and and a natural number such that , for all .

Alternatively, .

Example