Hypothesis Space Search by ID3

ID3 searches the space of possible decision trees: doing hill-climbing on information gain.
It searches the complete space of all finite discrete-valued functions. All functions have at least one tree that represents them.
It maintains only one hypothesis (unlike Candidate-Elimination). It cannot tell us how many other viable ones there are.
It does not do back tracking. Can get stuck in local optima.
Uses all training examples at each step. Results are less sensitive to errors.