Lower bounds on probabilistic linear decision trees (Q1067786)

Probabilistic linear one sided decision trees are examined. A technique is developed to derive lower bounds for the average number of comparisons in such trees from lower bounds on deterministic trees. Using it, \(\Omega\) (n lg n) lower bounds are derived for problems such as element uniqueness, set equality, etc. Standard lower bound arguments for deterministic decision trees are shown to be valid for probabilistic decision trees. Nevertheless, a simple problem is described where use of random choices provably saves time.