Time complexity of decision trees

Mikhail Ju Moshkov*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

70 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.

Original languageEnglish (US)
Title of host publicationTransactions on Rough Sets III
PublisherSpringer Verlag
Number of pages16
ISBN (Print)3540259988, 9783540259985
StatePublished - 2005
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3400 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


  • Decision tree
  • Rough set theory
  • Test theory
  • Time complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this