AFTD Auto-Formalizing Theoretical Domains

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 a has depth at most d, then comparison_tree_bind T f has depth at most comparison_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)
See it in the graphDiscuss this resultChallenge it