Average Time Complexity of Decision Trees

This monograph generalizes several known results on the topic and considers a number of fresh problems. Combinatorics, probability theory and complexity theory are used in the proofs, as well as concepts from discrete mathematics and computer science.