comparison_tree_depth
def
The depth of a comparison decision tree is the maximum number of comparisons along any branch from the root to a leaf.
Statement
def comparison_tree_depth {n : ℕ} : ComparisonTree n → ℕ- Defined in
- arXiv:2610.18740 Sec. 3.1
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 1
- ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
- Used by 7
- 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.
- comparison_tree_num_leaves_le_two_pow_depthFor any natural number n and any comparison decision tree T on n elements, the number of leaves of T is at most 2 raised to the depth of T.
- 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…
- 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…
- comparison_tree_depth_bind_leIf every continuation tree
f ahas depth at mostd, thencomparison_tree_bind T fhas depth at mostcomparison_tree_depth T + d:… - v_selection_posetFor a natural number n, a partial order P on Fin n, and a rank i, V_i(P) is the infimum of depths of all comparison decision trees on n…
Read back from the Lean
For any natural number n (implicit), comparison_tree_depth is the function that computes the depth of a ComparisonTree n as a natural number, defined recursively by:
- mapping any leaf .leaf ans to 0;
- mapping any branch .branch i j l r to 1 + max(comparison_tree_depth l, comparison_tree_depth r).
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 depth of a comparison decision tree, representing its worst-case comparison cost. -/ def comparison_tree_depth {n : ℕ} : ComparisonTree n → ℕ := fun | .leaf _ => 0 | .branch _ _ l r => 1 + max (comparison_tree_depth l) (comparison_tree_depth r)