Four half-size children with a linear toll have quadratic cost
ProvedCLRS.Chapter4Master.Examples.leafDominated_thetaLet be the constructed total recurrence with and
Then at natural infinity. The logarithm is natural and logarithmic exponents are real. This is a concrete numerical application of the discrete master theorem; it does not assert that a separate compiled source algorithm realizes the recurrence.
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_MasterApplications 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 open Filter Asymptotics Real namespace CLRS.Chapter4Master.Examples end CLRS.Chapter4Master.Examples open CLRS.Chapter4Master CLRS.Chapter4Master.Examples
theorem CLRS.Chapter4Master.Examples.leafDominated_theta :
leafDominated =Θ[atTop] fun n : ℕ => (n : ℝ) ^ (2 : ℕ) := by sorry