Big O Notation
The short answer · 19 words
In short
Mathematical notation for describing an asymptotic upper boundary for the growth of effort or functions with increasing input size.
Flow-alerta.cab (2026): Big O Notation. https://flow-alerta.cab/en/glossar/big-o-notation. Editorially reviewed on: 09 October 2026.
How much detail would you like?
Practical
Basis for algorithmic scalability and technical architectural decisions. Particularly useful when comparing search, sorting and data structure algorithms.
Example scenario: Binary search requires logarithmically growing search steps in a sorted list and is typically described by O(log n).
Use software with large amounts of data to identify early on which algorithms or data accesses could scale poorly; then supplement real measurements.
At a glance
- Core
- In computer science, Big O is often used to describe how the time or memory requirement of an algorithm grows with the problem size. Formally, f(n)=O(g(n)) means that f is bounded above by a constant multiple of g from a sufficiently large input. Colloquially, Big O is often used inaccurately as an exact runtime class.
- Use
- Basis for algorithmic scalability and technical architectural decisions. Particularly useful when comparing search, sorting and data structure algorithms.
- Example
- Example scenario: Binary search requires logarithmically growing search steps in a sorted list and is typically described by O(log n).
- Limits
- Understanding Big O as exact runtime; completely ignoring constants and real hardware; equating O and Θ; not distinguishing average and worst cases.
Questions about this term
Does Big O measure real seconds?
No.
Is an algorithm described with O(n²) always slower than one with O(n)?
No; O gives only upper limits. For a reliable comparison, suitable narrow limits and concrete conditions are needed.
Is O the same as Θ?
No.
All details and background
In computer science, Big O is often used to describe how the time or memory requirement of an algorithm grows with the problem size. Formally, f(n)=O(g(n)) means that f is bounded above by a constant multiple of g from a sufficiently large input. Colloquially, Big O is often used inaccurately as an exact runtime class.
ELI5 – Explained simply
Big O does not describe the seconds on a particular computer, but how much the effort grows when the input becomes larger.
Why it matters in practice
Basis for algorithmic scalability and technical architectural decisions. Particularly useful when comparing search, sorting and data structure algorithms.
Example
Example scenario: Binary search requires logarithmically growing search steps in a sorted list and is typically described by O(log n).
Pitfalls and limits
- Understanding Big O as exact runtime; completely ignoring constants and real hardware; equating O and Θ; not distinguishing average and worst cases.
Origin & history
The NIST dictionary defines O-notation as an asymptotic upper barrier. A narrow asymptotic barrier is denoted by Θ; O alone does not determine an exact growth rate.
Use in mid-sized companies
- Use software with large amounts of data to identify early on which algorithms or data accesses could scale poorly; then supplement real measurements.
Related terms
- Time complexity
- Memory complexity
Matching Flow-alerta service
Websites & web applicationsWebsites & web applications: technical implementation and testing of a suitable web application.Matching tool / use case
View use casesUse Case: Compare the scaling of two search or processing algorithms.Sources
- xlinux.nist.govNIST Dictionary of Algorithms and Data Structures, big-O notation
Quellenprüfung: 09.10.2026. Definition und dokumentierte Einordnung abgeglichen; Beispiele beschreiben mögliche Anwendungen.
Editorially reviewed on: