Big-O Notation

Khan Academy's short article gives a useful intuition for eventual upper bounds and loose versus tight descriptions, but it does not fully separate case functions from asymptotic relations or state the formal quantifiers.

budding confidence: certain planted 2026-08-21 tended 2026-08-21 asymptotic-analysisbig-osource-auditexplainer

article Big-O Notation Cormen, Thomas H., Balkcom, Devin, Khan Academy Computing Curriculum Team original

This Khan Academy article is a compact explanatory introduction to Big-O. It distinguishes Big-O from Big-Theta, introduces an eventual scaled upper bound, and uses binary search to show that one function can satisfy many true but differently informative upper bounds.

The complete article body was read in the browser, excluding the reader discussion from technical evidence. The page exposes no reliable publication or revision date; the current footer year is not an article date. The article credits Dartmouth computer-science professors Thomas Cormen and Devin Balkcom together with the Khan Academy computing curriculum team and states a CC-BY-NC-SA license. The normalized 3,436-character article body had SHA-256 ebd67429cd4470fa9a444469d6aad5f64a99f709f3d9a570c4a581791e5aaf06 during ingestion.

What the article contributes #

Big-O is an eventual asymptotic upper bound rather than an exact runtime formula.
A tight $\Theta(f)$ bound implies an $O(f)$ upper bound, but the converse need not hold.
A function in $\Theta(\log n)$ is also in $O(n)$ , $O(n^2)$ , and many larger classes; those looser statements are true but less informative.
Binary search provides an accessible contrast between best-case $\Theta(1)$ and worst-case $\Theta(\log n)$ comparison counts.
Its one explanatory graph conveys the central idea that the cost must remain below a scaled comparison function after some threshold.

Source claims audit #

Source claim or framing	Verdict	GTK treatment
Big-O gives an asymptotic upper bound	current	State the full $\exists c\,\exists n_0\,\forall n\ge n_0$ definition
Big-Theta gives matching upper and lower orders	current	Define $\Theta(g)=O(g)\cap\Omega(g)$ for the chosen cost function
Binary search has best-case $\Theta(1)$ and worst-case $\Theta(\log n)$ comparisons	current under the ordinary comparison model	Name the two case functions before applying asymptotic notation
Binary-search runtime is “never worse than $\Theta(\log n)$ ”	notation error	Use $O(\log n)$ for the upper-bound claim; reserve $\Theta$ for a tight function bound
Any $\Theta(f)$ claim is also an $O(f)$ claim	current	Explain class inclusion and preserve the direction
Binary search is also $O(n)$ , $O(n^2)$ , and $O(2^n)$	current but intentionally loose	Use this to distinguish truth from informativeness
A fixed-money analogy explains Big-O	partial intuition	Add the missing family of inputs, scaling function, threshold, and fixed multiplier

Visual audit #

The article contains one information-bearing 359 by 215 pixel graph. It plots a running-time curve against a scaled bound and indicates a threshold after which the bound holds. The concept is sound, but the threshold and vertical axis are not labeled, while its alt text names formulas not visible in the chart. GTK therefore does not retain it. The asymptotic-analysis chapter uses an original, theme-aware diagram that explicitly labels $f(n)$ , $c g(n)$ , $n_0$ , and the eventual inequality.

Editorial role #

This source is cited for the introductory intuition and the loose-bound example. The formal definitions, notation semantics, cost models, and proof obligations are grounded in Knuth, MIT course material, and NIST DLMF.

What the article contributes #

Source claims audit #

Visual audit #

Editorial role #

Related