Recurrence comparison from a common base range and toll bound
ProvedCLRS.Chapter4Master.Recurrence.comparisonA 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.
Take two such packages for and , with the same multiplier and child function. Let be at least both cutoffs, and let be any real constant. If below and from onward, then
The theorem preserves the supplied constant; it does not assume . Its explicit finite-range premises support comparisons whose original recurrences use different base cutoffs.
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.
Catalog organization (2026-10-11). This record was retired from the active Chapter 4 catalog to focus the presentation on three algorithms and four reusable recurrence results. Its mathematical statement and proof status are unchanged, and existing imports and links remain valid. The retained results are CLRS.Chapter4Master.master_theorem. Supporting lemmas needed by the retained results are included in their accepted proof files.
import Definitions.Def_CLRS_Chapter4_Master_Basic
import Mathlib.Analysis.Asymptotics.Theta
import Mathlib.Tactic
set_option autoImplicit false
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true
namespace CLRS
end CLRS
open CLRS
open Filter Asymptotics
open scoped Topology
namespace CLRS.Chapter4Master
end CLRS.Chapter4Master
open CLRS.Chapter4Master
namespace CLRS.Chapter4Master.Recurrence
end CLRS.Chapter4Master.Recurrence
open CLRS.Chapter4Master CLRS.Chapter4Master.Recurrence
variable {T f U g : ℕ → ℝ} {a : ℝ} {r : ℕ → ℕ}
theorem CLRS.Chapter4Master.Recurrence.comparison (R : Recurrence T f a r) (S : Recurrence U g a r)
{N : ℕ} (hRN : R.cutoff ≤ N) (hSN : S.cutoff ≤ N)
{C : ℝ} (hbase : ∀ n, n < N → T n ≤ C * U n)
(htoll : ∀ n, N ≤ n → f n ≤ C * g n) : ∀ n, T n ≤ C * U n := by sorry