AFTD Auto-Formalizing Theoretical Domains

v_selection

def

The minimum number of pairwise comparisons V_i(n) needed in the worst case by a deterministic comparison algorithm (decision tree) to find the i-th smallest element among n distinct elements, defined for 0 < i ∧ i ≤ n as the comparison selection complexity of 0-based rank i - 1 in Fin n, and 0 otherwise.

Statement

noncomputable def v_selection (n : ℕ) (i : ℕ) : ℕ
Defined in
scout/2610-18740-selecting-the-7th-smallest-of-16-elements-takes-exactly-28.md:Sec. 1
Verified
18 Oct 2026
Axioms
none listed
Built on 1
  • comparison_selection_complexityThe worst-case comparison complexity to select the element of rank r : Fin n among n elements, defined as the infimum of the depths of all…
Used by 3
  • v_selection_three_two_upper_boundThe 2nd smallest (the median) of 3 distinct elements can be found using at most 3 pairwise comparisons, that is, V_2(3) ≤ 3.
  • v_selection_le_iffFor any positive rank i ≤ n and bound d, the worst-case comparison complexity V_i(n) is at most d if and only if there exists a comparison…
  • v_selection_16_8_le_28_iff_exists_treeThe worst-case comparison complexity of selecting the 8th smallest element among 16 elements is at most 28 (that is, V_8(16) ≤ 28) if and…

Read back from the Lean

The function v_selection n i defines the worst-case comparison complexity $V_i(n)$ of selecting the $i$-th smallest element out of $n$ elements. For $0 < i \le n$, it evaluates to the minimum depth of a comparison tree on $n$ elements that correctly identifies the element of rank $i - 1$ (0-indexed) for all permutations of the inputs. If $i = 0$ or $i > n$, it returns $0$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The minimum worst-case comparison complexity V_i(n) to find the i-th smallest of n elements. -/
noncomputable def v_selection (n : ℕ) (i : ℕ) : ℕ := if h : 0 < i ∧ i ≤ n then comparison_selection_complexity (n := n) ⟨i - 1, by omega⟩ else 0
See it in the graphDiscuss this resultChallenge it