VC Dimension

A measure in statistical learning theory of the complexity of a hypothesis space, defined as the size of the largest sample set that the hypothesis space can shatter; it is commonly used in the analysis of generalization error bounds.