comparison_selection_complexity
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 }