There are prolific studies on complexity of classical machine learning models decades ago, which are summarized in excellent surveys [1]}, [2]}, [3]}, [4]}. In this section, we very briefly review the complexity of several typical models, including decision tree, logistic regression and bayesian network models. We also discuss the differences between the model complexity of deep neural networks and that of those models.
