Asymptotic resource bounds

Mathematical statement

For nonnegative functions f,g:N→R, f∈O(g) means that some c>0 and threshold N satisfy f(n)≤c·g(n) for every n≥N. The relation Ω is the corresponding lower bound, and Θ requires both. Input size and cost model are part of the claim.

Representative formula (exact TeX)

f(n)=g(n)

Assumptions

• Natural inputs n begin at 0; exercises explicitly state the function family and nonnegative coefficients.
• Every asymptotic conclusion requires a full-tail witness or a theorem for the declared family; finite benchmarks are observations only.

Symbol scope

• f — resource function to be bounded
• g — comparison function
• n — input size

Intuition, definition, and misconceptions

Big O is not an equality or a comparison at one n. Constant factors and finite prefixes are absorbed in witnesses.

For nonnegative-coefficient polynomials, the highest nonzero degree determines the Θ growth degree; the exercises retain zero-polynomial and constant boundaries separately.

Different cost models can give different resource functions for the same algorithm. Fix basic operations, input representation and size before comparing bounds.

Do not prove asymptotic relations from a few benchmark points or treat O, Ω and Θ as interchangeable.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Natural number — Natural numbers index input sizes.
• Arithmetic operations — Cost functions and witnesses use exact operations.
• Usual order on the real numbers — Upper and lower bounds are full-tail inequalities.
• Function mapping — Resources are functions of input size with nonnegative values.

Verification boundary

This slice establishes full-tail conclusions only in explicitly given nonnegative monomial/polynomial families; no general algorithmic complexity is inferred from finite measurements.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Bind standard asymptotic predicates, eventually filters and algorithmic cost functions with explicit witnesses.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.