Sample complexity

Similar to run time complexity it is the number of samples required for a model to converge to the optimum hypothesis in terms of the problem size.