Big o notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.

Overview

Big O notation characterizes functions according to their growth rates: different functions with the same 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 usually only provides an upper bound on the absolute value of the function.

Definition

Formally, let f and g be two functions defined on some subset of the real numbers. One writes

f(x) = O(g(x)) as x → ∞

if and only if there is a positive constant M such that for all sufficiently large values of x, the absolute value of f(x) is at most M multiplied by the absolute value of g(x). That is,

|f(x)| ≤ M |g(x)| for all x > x₀.

In many contexts, the assumption that x → ∞ is omitted and it is taken as understood that the behavior of the function is being described as x grows arbitrarily large.

Usage

Big O notation is used in many areas of computer science, particularly in algorithm analysis, computational complexity theory, and computer science. It provides a useful way to express the time complexity or space complexity of an algorithm, allowing the performance of different algorithms to be compared.

Examples

1. The function f(x) = 6x^4 - 2x^3 + 5, and g(x) = x^4 can be described by f(x) = O(x^4). 2. The time complexity of searching an element in a balanced search tree is O(log n) where n is the number of elements in the tree.

Related Concepts

Big O notation is often used in conjunction with other notations such as Big Omega notation (Ω), which provides a lower bound on the growth rate of a function, and Big Theta notation (Θ), which provides a tight bound on the growth rate.

See Also

• Computational complexity theory
• Analysis of algorithms
• Smoothed analysis
• Master theorem (analysis of algorithms)