Time complexity of decision trees

Research output: Contribution to journalArticlepeer-review

67 Scopus citations


The research monograph is devoted to the study of bounds on time complexity in the worst case of decision trees and algorithms for decision tree construction. The monograph is organized in four parts. In the first part (Sects. 1 and 2) results of the monograph are discussed in context of rough set theory and decision tree theory. In the second part (Sect. 3) some tools for decision tree investigation based on the notion of decision table are described. In the third part (Sects. 4-6) general results about time complexity of decision trees over arbitrary (finite and infinite) information systems are considered. The fourth part (Sects. 7-11) contains a collection of mathematical results on decision trees in areas of rough set theory and decision tree theory applications such as discrete optimization, analysis of acyclic programs, pattern recognition, fault diagnosis and probabilistic reasoning. © Springer-Verlag Berlin Heidelberg 2005.
Original languageEnglish (US)
Pages (from-to)244-259
Number of pages16
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3400 LNCS
StatePublished - Jan 1 2005
Externally publishedYes


Dive into the research topics of 'Time complexity of decision trees'. Together they form a unique fingerprint.

Cite this