document: On average depth of decision trees implementing Boolean functions The article considers the representation of Boolean functions in the form of decision trees . It presents the bounds on average time complexity of decision trees for all classes of Boolean functions that are closed over substitution , and the insertion and deletion of unessential variables . The obtained results are compared with the results developed by M.Ju . Moshkov -LRB- 1995 -RRB- that describe the worst case time complexity of decision trees
doc_bio_tags: O B I O B I O B I O O O O O O B I O O O O B I O O O O O O B I I O B I O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I I O B I
extractive_keyphrases: average depth decision trees boolean functions average time complexity worst case time complexity