We'd like to use analytics cookies to understand which symbols people look up, so we know what to research next. They are not used for advertising and we set none of them unless you say yes. What we store.
A capital O with a bracketed expression, bounding a growth rate from above.
Also known as: Order notation, Landau notation, Asymptotic notation, Complexity notation
Big O notation writes a capital O followed by a bracketed expression to bound how fast a quantity grows. It states an upper bound and not an exact rate, which is why an algorithm that is O(n) is also correctly O(n²). The equals sign conventionally written with it does not mean equality — the statement is a membership claim, and reversing it is meaningless. Related letters bound in other directions: Ω from below and Θ from both.
States an upper bound on a growth rate rather than an exact rate, which is why an algorithm correctly described as growing linearly is also, correctly if uselessly, described as growing no faster than quadratically.
Contexts: Mathematics, Software
Uses an equals sign that does not mean equality. The statement is a claim about membership of a class of functions, so it cannot be read backwards and cannot be chained the way a genuine equation can.
Contexts: Mathematics, Software
Belongs to a family that bounds in different directions: the capital Greek omega bounds from below, the capital theta bounds from both sides at once, and lower-case o states a strictly weaker bound than the capital.
Contexts: Mathematics, Software
A capital letter O followed immediately by a rounded bracket enclosing a short expression, with no space between the letter and the bracket.
Both belong to the language of limiting behaviour.