Lecture 06: Asymptotics

MIT's 2024 Mathematics for Computer Science notes give modern definitions and equivalences for the full Landau-notation family, while carefully audited local defects show why their limit tests and sign conventions need qualification.

budding confidence: certain planted 2026-08-21 tended 2026-08-21 asymptotic-analysisbig-olittle-obig-omegalittle-omegabig-thetasource-audit

docs Lecture 06: Asymptotics Abel, Zachary, Chapman, Brynmor, Demaine, Erik · 2024 originalarchived pdf

This official MIT 6.1200J/18.062J Mathematics for Computer Science lecture develops asymptotic comparison from harmonic numbers and factorial estimates, then gives definitions, equivalences, sufficient limit tests, and notation warnings for $\sim$ , $O$ , $o$ , $\Omega$ , $\omega$ , and $\Theta$ . GTK uses its physical pages 7–13 as a modern explanatory source for the strict relations that Knuth's 1976 historical note does not define in today's form.

All 14 physical pages were read and visually inspected. The notes display the byline Z. Abel, B. Chapman, and E. Demaine; MIT's course page resolves those names as Zachary Abel, Brynmor Chapman, and Erik Demaine. The PDF metadata misspells Zachary as Zahcary, so the corrected official spelling is used in the registry. The archived file has SHA-256 fee591c38d5913ac4e4a249e6a6db5f28b969fea695e45f859a3b75996a3fae3 and is byte-identical to the retrieved PDF.

What the notes contribute #

Physical page 7 defines eventual Big-O on the positive integers and makes the function domains explicit.
Physical page 9 gives both the ratio-limit and quantified- $\varepsilon$ forms of little- $o$ .
Physical pages 10–11 define Big-Omega by reversed Big-O, define little- $\omega$ by reversed little- $o$ , and prove the ratio and every-constant formulations under positivity assumptions.
Physical page 11 defines $\Theta(g)=O(g)\cap\Omega(g)$ .
Physical page 12 treats asymptotic expressions as function sets and explains why conventional equality notation is not symmetric equality.
Physical page 13 summarizes six relations and, through color, distinguishes definitions or equivalences from limit criteria that are only sufficient.

Source claims audit #

Source claim or framing	Verdict	GTK treatment
Big-O allows a witness $c\in\mathbb R$	nonstandard but extensionally harmless under the source's positive $g$	Normalize the definition to $c>0$
A finite limit of $	f	/g$ characterizes Big-O
On $\mathbb Z_{>0}$ , an eventual bound can be extended over every input	current on this discrete domain	The finite exceptional prefix has a maximum ratio; do not export this to an arbitrary continuous domain
$f\in o(g)$ iff every $\varepsilon>0$ eventually gives $	f	<\varepsilon g$
$f\in\omega(g)$ iff $g\in o(f)$ iff every $c>0$ is eventually beaten	current under positivity	Use the chapter's eventual-nonnegative cost-function convention
$\Theta(g)=O(g)\cap\Omega(g)$	current	Present it as simultaneous upper and lower bounds, not ratio convergence to one
Defining $\Omega$ by $g\in O(f)$ needs no sign qualification	source convention is stronger than necessary	GTK states direct eventual lower-bound inequalities for eventually nonnegative costs
“about $\log_2$ multiplications rather than $n$ ”	visible source error	The missing argument is $\log_2 n$ ; the sentence is not reused
Dropping the refined Stirling correction has multiplicative error below $1+1/(144n^2)$	ambiguous	The stated factor can describe the width between correction bounds, not the $O(1/n)$ relative error from deleting the correction itself
Repeated squaring makes the Stirling computation “extremely efficient”	underspecified	A real complexity claim must also price arithmetic precision, roots, exponentials, and output size
The $4^x$ versus $2^x$ contradiction follows from only $x>\max(c,M)$	minor proof gap	Also require $x$ large enough that $2^x>x$ ; the conclusion remains correct

Visual audit #

Two visuals carry information. Physical page 1 has a labeled block-stack geometry diagram that is clear but outside this chapter's notation scope. Physical page 13 has a color-coded summary table in which red rows are merely sufficient limit tests and black rows are definitions or equivalences. Plain extraction loses that distinction. Neither source visual is retained: GTK's native comparison table states the quantifiers directly and keeps sufficient limit tests out of the definitions.

Editorial role #

This source supports modern strict $o/\omega$ semantics and the distinction between definitions, equivalences, and sufficient limit tests. It is not used for machine-model claims, exact arithmetic costs, or an unqualified global sign convention.

What the notes contribute #

Source claims audit #

Visual audit #

Editorial role #

Related