Is there a clear relationship between number of training examples and over/underfitting when you do not know the model complexity? It seems that without knowing the model complexity, it is difficult to state for certain what is the relationship between the number of training examples and over/underfitting.
As a concrete example, suppose that I have some unspecified class of model. I have 1000 data at my disposal. Suppose we partition the data into N training examples and train a classifier based on these N points.
Now supposed that N is small (e.g., 200) will I have overfitting or underfitting? Similarly, suppose N is large (e.g., 800), what is the answer to the above question? 
It seems logically plausible that both might occur. 
Can someone chime in and come up with some example where one or the other might occur (or both)?
 A: The degree of overfitting/underfitting is measured by the complexity between your proposed model and the true model. We cannot know whether the model will overfit/underfit by simply changing the number of data points.
Suppose the only tuning parameter of the model complexity is the number of predictors, $k$. Further suppose you have a training set, which is a dataset for estimating the parameters of your model, and a validation set, which is a dataset just for evaluating the accuracy of the predicted response and tuning your model. You can then find the accuracy, which is a metric of closeness between the all true responses and their corresponding predictions of the data in a dataset, for both the training set and the validation set. 
In the context of machine learning, you can say that your proposed model with number of predictors $k$:


*

*overfits if you observe that the training accuracy is higher than the validation accuracy

*underfits if you observe that the training accuracy is less than the validation accuracy

