AFTD Auto-Formalizing Theoretical Domains

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

/-- 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
See it in the graphDiscuss this resultChallenge it