Cslib.Algorithms.Lean.TimeM.timeMergeSortRec_le
theoremverifiedformalizationimported Lean
Solve the recurrence
Statement
set_option relaxedAutoImplicit true in open Cslib Cslib.Algorithms Cslib.Algorithms.Lean Cslib.Algorithms.Lean.TimeM in set_option autoImplicit false in variable {α : Type} [LinearOrder α] in open Nat (clog) in theorem Cslib.Algorithms.Lean.TimeM.timeMergeSortRec_le (n : ℕ) : timeMergeSortRec n ≤ T n
- Formalizes
- CSLib, `Cslib.Algorithms.Lean.TimeM.timeMergeSortRec_le`
- Lean proof
- By Sorrachai Yingchareonthawornhcai, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2025 Sorrachai Yingchareonthawornhcai. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.Cslib.Algorithms.Lean.TimeM.timeMergeSortRec_le← Cslib.Algorithms.Lean.TimeM.timeMergeSortRec_le (Cslib/Algorithms/Lean/MergeSort/MergeSort.lean:162): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 27
- Cslib.Algorithms.Lean.TimeM.ret_mergeOur merge computes the one already in mathlib.
- Cslib.Algorithms.Lean.TimeM.timeMergeSortRecRecurrence relation for the time complexity of merge sort. For a list of length
n, this counts the total number of comparisons: - Base… - Cslib.Algorithms.Lean.TimeM.TUpper bound function for merge sort time complexity:
T(n) = n * ⌈log₂ n⌉ - Cslib.Algorithms.Lean.TimeM.some_algebraCslib.Algorithms.Lean.TimeM.some_algebra
- Cslib.Algorithms.Lean.TimeMA monad for tracking time complexity of computations.
TimeM T αrepresents a computation that returns a value of typeαand… - Cslib.Algorithms.Lean.TimeM.ret_pureCslib.Algorithms.Lean.TimeM.ret_pure
- Cslib.Algorithms.Lean.TimeM.ret_bindCslib.Algorithms.Lean.TimeM.ret_bind
- Cslib.Algorithms.Lean.TimeM.ret_mapCslib.Algorithms.Lean.TimeM.ret_map
- Cslib.Algorithms.Lean.TimeM.ret_seqRightCslib.Algorithms.Lean.TimeM.ret_seqRight
- Cslib.Algorithms.Lean.TimeM.ret_seqLeftCslib.Algorithms.Lean.TimeM.ret_seqLeft
- Cslib.Algorithms.Lean.TimeM.ret_seqCslib.Algorithms.Lean.TimeM.ret_seq
- Cslib.Algorithms.Lean.TimeM.time_bindCslib.Algorithms.Lean.TimeM.time_bind
- Cslib.Algorithms.Lean.TimeM.time_pureCslib.Algorithms.Lean.TimeM.time_pure
- Cslib.Algorithms.Lean.TimeM.time_mapCslib.Algorithms.Lean.TimeM.time_map
- Cslib.Algorithms.Lean.TimeM.time_seqRightCslib.Algorithms.Lean.TimeM.time_seqRight
- Cslib.Algorithms.Lean.TimeM.time_seqLeftCslib.Algorithms.Lean.TimeM.time_seqLeft
- Cslib.Algorithms.Lean.TimeM.time_seqCslib.Algorithms.Lean.TimeM.time_seq
- Cslib.Algorithms.Lean.TimeM.ret_tickCslib.Algorithms.Lean.TimeM.ret_tick
- Cslib.Algorithms.Lean.TimeM.time_tickCslib.Algorithms.Lean.TimeM.time_tick
- Cslib.Algorithms.Lean.TimeM.instPureOfZeroCslib.Algorithms.Lean.TimeM.instPureOfZero
- Cslib.Algorithms.Lean.TimeM.instBindOfAddCslib.Algorithms.Lean.TimeM.instBindOfAdd
- Cslib.Algorithms.Lean.TimeM.instFunctorCslib.Algorithms.Lean.TimeM.instFunctor
- Cslib.Algorithms.Lean.TimeM.instSeqOfAddCslib.Algorithms.Lean.TimeM.instSeqOfAdd
- Cslib.Algorithms.Lean.TimeM.instSeqLeftOfAddCslib.Algorithms.Lean.TimeM.instSeqLeftOfAdd
- Cslib.Algorithms.Lean.TimeM.instSeqRightOfAddCslib.Algorithms.Lean.TimeM.instSeqRightOfAdd
- Cslib.Algorithms.Lean.TimeM.instMonadOfAddZeroCslib.Algorithms.Lean.TimeM.instMonadOfAddZero
- Cslib.Algorithms.Lean.TimeM.instLawfulMonad
TimeMis lawful so long as addition in the cost is associative and absorbs zero.
- Used by 1
- Cslib.Algorithms.Lean.TimeM.mergeSort_timeTime complexity of mergeSort
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit true inopen Cslib Cslib.Algorithms Cslib.Algorithms.Lean Cslib.Algorithms.Lean.TimeM inset_option autoImplicit false invariable {α : Type} [LinearOrder α] inopen Nat (clog) in/-- Solve the recurrence -/theorem Cslib.Algorithms.Lean.TimeM.timeMergeSortRec_le (n : ℕ) : timeMergeSortRec n ≤ T n := by fun_induction timeMergeSortRec with | case1 => grind | case2 => grind | case3 n ih2 ih1 => grw [ih1,ih2] have := some_algebra n grind [Nat.add_div_right]