--- title: "Asymptotic Notation Made Precise" description: "The definition behind big-O: f(n) is O(g(n)) when some constant multiple of g stays above f from some input size onward. Big-Omega bounds from below and big-Theta bounds from both sides, so a claim ab" canonical: https://lightmysky.com/learn/computing/asymptotic-notation-made-precise-mt_B0Z6Syy8Ve source: https://lightmysky.com/learn/computing/asymptotic-notation-made-precise-mt_B0Z6Syy8Ve.md retrieved: 2026-09-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Asymptotic Notation Made Precise The definition behind big-O: f(n) is O(g(n)) when some constant multiple of g stays above f from some input size onward. Big-Omega bounds from below and big-Theta bounds from both sides, so a claim about growth becomes something a student can argue for rather than assert. Subject: Computing · Area: Algorithms & Data Structures · Ages 18 to 19 Page: https://lightmysky.com/learn/computing/asymptotic-notation-made-precise-mt_B0Z6Syy8Ve ## Ready when they can - Name a constant and a starting size that make a given big-O claim true - Say what big-Omega and big-Theta each add to a big-O statement - Explain why an O(n squared) method can still beat an O(n) one on small inputs ## Lesson: What big-O really promises Big-O is a promise about the long run. Saying a running time is O of g means some constant multiple of g never drops below it once inputs are big enough. It is an upper bound from some starting size onward, not an exact prediction for every input. **Example.** Take 5 n squared plus 30 n. Six copies of n squared stay above it from n equal to 30 onward, because the extra 30 n fits inside one n squared once n reaches 30. So the constant 6 with starting size 30 makes the O of n squared claim true. The same function is not O of n, since the n squared term outgrows every constant multiple of n. Big-Omega bounds from below: the running time stays above some constant multiple, so it certifies a minimum. Big-Theta does both at once, sandwiching the running time between two multiples. Binary search is honestly O of log n, not Theta of log n, because a lucky first guess finishes in constant time. A minimum grabbed from index 0 of a sorted list takes the same single step always, so it is Theta of 1. **Tip.** An O of n squared method with tiny constants can beat an O of n method with huge ones while n is small. Only past the crossover point does slower growth always win. So claim O when you hold an upper bound, and save Theta for when you can justify the lower bound too. **Recap.** Use O for an upper bound, Omega for a lower bound, and Theta only when you can sandwich both sides. ## Practice 8 questions on this page, each with its working shown. ## Needs first - [L'Hopital's Rule and Comparing Growth Rates](https://lightmysky.com/learn/mathematics/lhopitals-rule-and-comparing-growth-rates-mt_Ai-A2sPIoE) - [Loop Invariants and Proving an Algorithm Correct](https://lightmysky.com/learn/computing/loop-invariants-and-proving-an-algorithm-correct-mt_fWnstju2ns) - [Counting Operations to Compare Algorithms](https://lightmysky.com/learn/computing/counting-operations-to-compare-algorithms-mt_JkN961niFG) - [Big-O Notation and Orders of Growth](https://lightmysky.com/learn/computing/big-o-notation-and-orders-of-growth-mt_mkqgxhJ509) - [Proof by Contradiction and Counterexample](https://lightmysky.com/learn/mathematics/proof-by-contradiction-and-counterexample-mt_pbFTv4v6k8) ## Opens up - [Recurrence Relations and the Master Theorem](https://lightmysky.com/learn/computing/recurrence-relations-and-the-master-theorem-mt_aOvLPV7rR8) - [Reading a Query Plan](https://lightmysky.com/learn/computing/reading-a-query-plan-mt_spbbzsCoBB)