Abstract
Mitchell's original work on version spaces [Mitchell, 1982] presented an analysis of the computational complexity of version spaces. However, this analysis proved somewhat coarse, as it was parameterized by s and g, the maximum sizes that the S and G sets reach during learning. As has been pointed out by Haussler [1988], g can be exponential in the number of examples processed. This paper presents a more fine-grained analysis of the computational complexity of version spaces, demonstrates its equivalence to Mitchell's analysis, and instantiates it for two commonly used conjunctive concept description languages.