AFTD Auto-Formalizing Theoretical Domains

comparison_selection_complexity

def

The 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 comparison decision trees T : ComparisonTree n that satisfy comparison_tree_selects_rank T r.

Statement

noncomputable def comparison_selection_complexity {n : ℕ} (r : Fin n) : ℕ
Defined in
scout/2610-18740-selecting-the-7th-smallest-of-16-elements-takes-exactly-28.md:Sec. 3
Verified
18 Oct 2026
Axioms
none listed
Built on 3
  • comparison_tree_selects_rankA comparison decision tree T on n elements (T : ComparisonTree n) correctly selects the element of rank r : Fin n if for every permutation…
  • comparison_tree_depthThe depth of a comparison decision tree is the maximum number of comparisons along any branch from the root to a leaf.
  • ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
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_selectionThe minimum number of pairwise comparisons V_i(n) needed in the worst case by a deterministic comparison algorithm (decision tree) to find…

Read back from the Lean

The declaration defines comparison_selection_complexity, which takes an implicit natural number n and an explicit r : Fin n, and returns a natural number. It is defined as the infimum (in ℕ, i.e., the minimum) of the set of all depths d : ℕ for which there exists a comparison tree T : ComparisonTree n such that: 1. T selects rank r: for every permutation σ : Equiv.Perm (Fin n), evaluating T on input σ produces an index whose value under σ is equal to r (i.e., σ (comparison_tree_eval σ T) = r). 2. The depth of T is equal to d (comparison_tree_depth T = d). Here, tree evaluation recursively starts at the root: at a branch comparing indices i and j, it branches to the left subtree if σ i < σ j and to the right subtree otherwise; at a leaf with answer ans, it returns ans. The depth of a tree is 0 at a leaf, and 1 plus the maximum of the depths of its left and right subtrees at a branch.

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

/-- Worst-case comparison complexity to select the element of 0-based rank r in Fin n. -/
noncomputable def comparison_selection_complexity {n : ℕ} (r : Fin n) : ℕ := sInf { d : ℕ | ∃ T : ComparisonTree n, comparison_tree_selects_rank T r ∧ comparison_tree_depth T = d }
See it in the graphDiscuss this resultChallenge it