Big O notation
Big O notation is a mathematical notation that describes the approximate size of a function on a domain.
At a glance
Key signals
0% cross fields · reaches 0 more
- Computer Science
- Algorithms
- Computational Complexity
- Explanation
- Examples
- Misconception
- Sourced relations
- Attribution
Dependencies
What this concept builds on and what it makes possible — derived from the atlas’s dependency, causal and structural relations, not from every related edge.
Enables · leads to
Space ComplexityrequiresBig O notationEstablished
Space Complexity requires Big-O Notation.
Time ComplexityrequiresBig O notationEstablished
Time Complexity requires Big-O Notation.
System context
Big O notationis part ofAnalysis of algorithmsEstablished
big O notation is part of analysis of algorithms.
Mechanism: Big O notation describes how an algorithm's running time grows with input size, ignoring constant details.
- Wikipedia (English & German editions) verifiedmoderate evidence
Structural role & consequence
Interpreted from the current atlas graph — what the connections mean, not just how many there are.
Currently dark in the atlas: no key date stored · 3 of 3 of its relations lack claim-level evidence.
atlas representation · Describes the current Thinking OS representation, not the state of the world.
Structural neighbourhood: 3 → 7 → 20 concepts reachable within 3 hops.
structural · Structural reach — being reachable is not the same as being understood.
All 3 of its relationships stay within its own discipline — a field-specific concept in the current atlas.
structural · Structural graph analysis — not a claim of importance, causation or history.
cross-field
3 within-field, 0 cross-field
Strengths & constraints
Constraints
- Evidence coverage currently thin in the atlas — few of its relationships carry claim-level evidence. atlas representation
- No dated history stored — the atlas records no key date for this concept. atlas representation
Conditions
- Read structurally — most of its relationships carry no external evidence yet, so claims here are graph-derived. structural
Dependency radial
What this concept builds on (left) and what it makes possible (right) — derived from dependency and causal relations.
What builds on this
2 concepts build on this directly, 3 in total, across 2 disciplines.
Structural downstream reach along dependency edges — not a claim of historical necessity.
Seen through each discipline
How this concept sits in each of its fields — derived from its real connections in the graph, not asserted.
Through this lens it connects to Analysis of algorithms.
Through this lens it connects to Analysis of algorithms.
Through this lens it connects to Time Complexity and Space Complexity.
Formula
Source: Wikidata
Check yourself
A quick check against a common misconception. Nothing is scored — picking the tempting-but-wrong answer just flags an idea worth revisiting.
Which statement is correct?
Big O tells you how many seconds an algorithm will take.
Big O describes growth, not absolute time. An O(n²) algorithm can beat an O(n·log n) one on small inputs; Big O only says who wins as the input grows large.
Look for: Learner reads Big O as a stopwatch time rather than a growth rate.
Related ideas to explore
Concepts that look related but are not yet connected here — candidates for a connection to reason about, not established links.
This idea also appears in…
The same structure shows up in other disciplines. These are real recurrences drawn from the graph — a starting point for asking “what carries over, and what changes?”
Scale30 disciplines · 45 concepts
Concepts
shares a mental model
shares a mental model
shares a mental model
shares a mental model
shares a mental model
shares a mental model
Big O notation is a shorthand for how an algorithm's work grows as the input gets bigger. O(n) means the effort grows in step with the data; O(n²) means it grows with the square — doubling the input quadruples the work.
Big O gives an asymptotic upper bound on an algorithm's growth rate, ignoring constant factors and lower-order terms. It lets you compare algorithms by how they scale, not by their speed on one machine — the language of algorithmic complexity.
Mental models at work here
- Connects 3 other ideas across 3 disciplines.
- Most of its connections are of the “Dependency” kind.
- It exercises 1 reusable thinking pattern.
Derived from the graph’s real structure — observations, not a score.
Sources
- Wikipedia (English & German editions) verifiedmoderate evidence
- Wikidata verifiedmoderate evidence