Big O Notation

The Wikipedia article is a broad map of asymptotic notation, history, examples, and neighboring conventions, but it mixes mathematical domains and computational models and is not used as formal authority.

budding confidence: certain planted 2026-08-21 tended 2026-08-21 asymptotic-analysisnotationhistorysource-auditreference

article Big O Notation Contributors to Wikimedia Projects · 2026 original

The Wikipedia article covers far more territory than an introductory algorithms chapter should: global and eventual definitions, finite-limit error terms, multivariate bounds, algebraic properties, common growth classes, $o$ , $\omega$ , $\Theta$ , two incompatible traditions for $\Omega$ , asymptotic equivalence, soft-O, history, and notation disputes. That breadth makes it a useful map and bibliography, not a load-bearing technical source.

The complete current revision 1368704842 was read in the browser, including every substantive section, both technical tables, citations, and further-reading entries. The revision was last modified on 2026-08-10 at 16:42 UTC. The normalized heading-plus-section text had SHA-256 07e8addefdca64ebdf827e8ba64f724ab60405497f1fe9a3561ba1f435da27aa during ingestion.

What the article contributes #

It exposes the set interpretation $f\in O(g)$ and the problem with reading the conventional equals sign as symmetric equality.
It supplies examples with explicit witness constants, finite-limit error terms, and multivariate uniformity.
It maps the algebra of asymptotic classes and the standard hierarchy from logarithmic through factorial growth.
It distinguishes the computer-science meanings of $\Omega$ and $\Theta$ from older analytic-number-theory conventions.
It gives bibliographic leads from Bachmann and Landau through Hardy, Vinogradov, and Knuth.

Source claims audit #

Source claim or framing	Verdict	GTK treatment
Big-O can be defined as a bounded ratio on an explicit domain	current	Use the eventual natural-number version appropriate to algorithmic cost functions
The eventual definition is “somewhat conflicting” with a global-domain version	convention-dependent framing	State the domain and limiting process directly; do not present one convention as universally primary
$O(g)$ is a class of functions and $f\in O(g)$ is the precise membership form	current	Prefer membership notation while acknowledging conventional one-way equality
Algebraic sum, product, and transitivity laws hold	current with hypotheses	State eventual nonnegativity or absolute-value conditions and expose cancellation traps
The table of growth classes orders common runtimes	useful but mixed	Rebuild a smaller table whose assumptions and mechanisms are explicit
Interpolation search is average $O(\log\log n)$	distribution-dependent	Omit from the foundation table unless the uniform-key assumption is stated
Comparison sorting is $O(n\log n)$	incomplete model statement	Separate constructive upper bounds from the $\Omega(n\log n)$ comparison lower bound
$f=o(F),g=o(G)$ implies $f+g=o(F+G)$	requires denominator/sign conditions	Do not teach the unqualified form
Soft-O has one stable universal definition	false	Note only that conventions vary when the notation is encountered
Historical $\Omega$ variants belong in an algorithms introduction	accurate but distracting	Mention the convention clash briefly and keep the number-theory family outside the core chapter

Visual audit #

The page contains two information-bearing tables: one lists 15 growth classes with examples; the other compares 12 asymptotic notations and their quantifiers. Both mix domains, models, and specialist conventions, so neither is retained. Hundreds of SVG images are rendered equations rather than independent diagrams. The only thematic raster image is a small decorative rendering of O(·), ~ and has no explanatory role.

Editorial role #

GTK uses this source to confirm topic coverage, terminology variants, historical leads, and common misconceptions. Formal definitions and algorithmic claims are independently sourced from primary papers and official university or NIST material.

What the article contributes #

Source claims audit #

Visual audit #

Editorial role #

Related