An eventual toll bound transfers to positive divide-and-conquer recurrences
ProvedCLRS.Chapter4Master.Recurrence.isBigO_of_toll_isBigOA 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 positive multiplier and child function. Their cutoffs and positive base values may differ. Then
The comparisons are eventual at natural infinity. No common prescribed bound on the two initial base ranges is an extra assumption; their finiteness and positivity are enough. This transfers an asymptotic toll estimate to the whole recurrence without smoothness assumptions on the original toll.
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.isBigO_of_toll_isBigO (R : Recurrence T f a r) (S : Recurrence U g a r)
(hfg : f =O[atTop] g) : T =O[atTop] U := by sorry