CLRS Chapter 4, §4.5: the three master-theorem cases with rounded natural sizes
ProvedCLRS.Chapter4Master.master_theoremA recurrence package consists of real-valued costs , a positive real multiplier , a natural child function , and a positive cutoff . It requires positive base costs for every , nonnegative toll at every size, strictly smaller children above the cutoff, and there.
Bounded-error rounding means a real divisor and a uniform real bound on for every natural size. All asymptotic comparisons are eventual as natural tends to infinity.
Assume additionally and put . The following three implications hold for this same recurrence:
- For every real , if , then .
- For every real , if , then .
- For every real and , if and eventually , then .
The logarithm is natural except in . Floor and ceiling division are available instances of bounded-error rounding; recursive decrease remains a separate premise in the recurrence package. In case three, regularity is checked at the actual rounded child, not an unrounded real argument. Cases one and two do not require monotonicity or smoothness of the original toll. Positive base costs include size zero, so a numerical recurrence with does not directly fit this package.
This is a reusable theorem about numerical cost functions. Applying it to a program additionally requires proof that a terminating execution has the stated recurrence. It formalizes the selected §4.5 discrete result; it does not claim coverage of §§4.6–4.7.
Platform namespace. The imported Chapter 4 source declarations live under CLRS in this upload to avoid collisions with independently published compiler versions. The immutable source reference retains the original declaration names.
import Definitions.Def_CLRS_Chapter4_Master_Basic import Definitions.Def_CLRS_Chapter4_Master_CaseTwo import Definitions.Def_CLRS_Chapter4_Master_Rounding import Definitions.Def_CLRS_Chapter4_Substitution import Mathlib.Analysis.Asymptotics.Theta import Mathlib.Analysis.Calculus.Deriv.MeanValue import Mathlib.Analysis.PSeries import Mathlib.Analysis.SpecialFunctions.Pow.Asymptotics import Mathlib.Analysis.SpecialFunctions.Pow.Deriv import Mathlib.Analysis.SpecialFunctions.Pow.Real import Mathlib.Computability.AkraBazzi.AkraBazzi import Mathlib.Tactic import Std set_option autoImplicit false set_option backward.isDefEq.respectTransparency false set_option backward.defeqAttrib.useBackward true namespace CLRS end CLRS open CLRS namespace CLRS.Chapter4Master end CLRS.Chapter4Master open CLRS.Chapter4Master open Filter Asymptotics Real
theorem CLRS.Chapter4Master.master_theorem {T f : ℕ → ℝ} {a b : ℝ} {r : ℕ → ℕ}
(R : Recurrence T f a r) (hr : RoundedDivision b r) (ha : 1 ≤ a) :
(∀ ε : ℝ, 0 < ε →
f =O[atTop] (fun n : ℕ => (n : ℝ) ^ (logb b a - ε)) →
T =Θ[atTop] (fun n : ℕ => (n : ℝ) ^ logb b a)) ∧
(∀ k : ℝ, 0 ≤ k →
f =Θ[atTop] (fun n : ℕ => (n : ℝ) ^ logb b a * (log n) ^ k) →
T =Θ[atTop] (fun n : ℕ => (n : ℝ) ^ logb b a * (log n) ^ (k + 1))) ∧
(∀ ε c : ℝ, 0 < ε → c < 1 →
(fun n : ℕ => (n : ℝ) ^ (logb b a + ε)) =O[atTop] f →
(∀ᶠ n in atTop, a * f (r n) ≤ c * f n) → T =Θ[atTop] f) := by sorry