This article was automatically translated from the original Turkish version.

Big-O Notation

+2 More

Big-O Notation is one of the fundamental asymptotic analysis tools used in computer science to measure the efficiency of algorithms. This notation formally describes how an algorithm’s running time or memory usage grows in relation to the input size. Big-O is used to define an upper bound on a function and has thus become a fundamental unit of measurement in algorithmic complexity analysis.

The term is derived from the German word Ordnung (order, rank) and was introduced by Paul Bachmann in 1894 in his work Analytische Zahlentheorie. It became an indispensable element of modern algorithm analysis following Donald Knuth’s systematic adoption of the concept in computer science.

Basic Definition of Big-O Notation

When a function f(n) is expressed in terms of another function g(n) using Big-O notation, it is written as f(n) = O(g(n)). This means that f(n) cannot exceed a constant multiple of g(n). More formally:

Definition: f(n) = O(g(n)) if and only if there exist positive constants c and k such that:

0≤f(n)≤c∗g(n),∀n≥k

Here, the constants c and k are fixed and independent of n. This definition captures the core purpose of Big-O: to understand how an algorithm behaves in its worst-case scenario.

Asymptotic Upper Bound

The primary function of Big-O notation is to show how an algorithm’s running time or memory requirement grows as a function of input size. In this context, the concept of an asymptotic upper bound represents the maximum performance value an algorithm can reach in its worst case. This does not mean the algorithm always consumes this amount of time; rather, it guarantees that under the most unfavorable conditions, the algorithm will not exceed this bound.

Formally, the asymptotic upper bound for a function f(n) is expressed as:

f(n)=O(g(n))=>∃c>0,∃k≥0,∀n≥k:0≤f(n)≤c∗g(n)

Here, g(n) serves as the comparison function and acts as a reference for controlling the growth rate of f(n). The constants c and initial point k depend solely on the functions f and g, not on n. Thus, the analysis reveals the algorithm’s fundamental growth trend independent of hardware, programming language, or compiler.

Properties of Big-O

The theoretical power of Big-O notation rests on several fundamental properties:

Reflexivity

Every function belongs to the same class as itself:

Transitivity

Growth classes can be chained:

Constant Factor Rule

Constants do not affect asymptotic growth:

Sum Rule

f(n)=O(h(n)),g(n)=O(k(n))⟹f(n)+g(n)=O(maxh(n),k(n))

Product Rule

f(n)=O(h(n)),g(n)=O(k(n))⟹f(n)⋅g(n)=O(h(n)⋅k(n))

Algorithm Complexities

An algorithm’s complexity is typically expressed in terms of input size n. Some common classes include:

O(1): Constant time — e.g., array indexing.
O(log n): Logarithmic — e.g., binary search.
O(n): Linear — e.g., linear search.
O(n log n): Log-linear — e.g., merge sort.
O(n²): Quadratic — e.g., bubble sort.
O(2ⁿ): Exponential — e.g., generating subsets.
O(n!): Factorial — e.g., generating all permutations.

Relation to Computational Complexity Theory

Big-O notation is foundational to computational complexity theory. The complexity classes P and NP are defined in terms of polynomial-time solvability (O(n^c)) versus exponential or factorial time (O(2ⁿ), O(n!)).

An algorithm running in polynomial time (O(n^k)) is generally considered feasible. Otherwise, the problem may be classified as NP-hard or NP-complete.

Limitations of Asymptotic Behavior: An Automata Theory Example

Some source texts discuss specialized uses of Big-O and Big-Θ in automata theory. In certain weighted automata, testing a state in Big-O terms can be converted to Big-Θ. Cook and Karp reductions demonstrate that one decision problem can be solved via another.

Additionally, the concept of “Eventually Big-O” specifies that Big-O bounds must hold for words of infinite length. In some semirings (e.g., tropical semiring), such containment problems can be decided, while in others they remain undecidable.0≤f(n)≤c∗g(n),∀n≥k

Author Information

AuthorBeyza Nur TürküDecember 3, 2025 at 7:19 AM

Discussions

No Discussion Added Yet

Start discussion for "Big-O Notation" article

View Discussions

Basic Definition of Big-O Notation
- Asymptotic Upper Bound
- Properties of Big-O
  - Reflexivity
  - Transitivity
  - Constant Factor Rule
  - Sum Rule
  - Product Rule
Algorithm Complexities
- Relation to Computational Complexity Theory
- Limitations of Asymptotic Behavior: An Automata Theory Example