pm_alg_cost_le
theoremverifiedformalization
The algorithm makes at most 2n − 3 queries (for n ≥ 2).
Statement
theorem pm_alg_cost_le (n : ℕ) (hn : 2 ≤ n) (P : PMPoset n) :
((pmAlg (n := n) n 0 []).cost P : ℤ) ≤ 2 * (n : ℤ) - 3- Formalizes
- Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4, Theorem 11 (at most wn queries, here w = 2); counted exactly for the same algorithm as at most 2n - 3 (the first element needs no query, the second one)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
- PMTree.costThe number of queries the algorithm T makes on the poset P.
- pmAlgThe candidate-list algorithm (Theorem 11 of arXiv 0707.1532, for width 2): scan the elements in order, keeping the (at most two) minimal…
- pm_alg_costCost bound: at most two queries per element, one for the second element, none for the first.
- Used by 1
- pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…
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.
/-- The algorithm makes at most `2n − 3` queries (for `n ≥ 2`). -/theorem pm_alg_cost_le (n : ℕ) (hn : 2 ≤ n) (P : PMPoset n) : ((pmAlg (n := n) n 0 []).cost P : ℤ) ≤ 2 * (n : ℤ) - 3 := by have := pm_alg_cost P n 0 [] (by simp) simp at this have h2 : (2 : ℤ) ≤ n := by exact_mod_cast hn rcases this with h | h · rw [h]; push_cast; omega · exact h