# Computational complexity of learning (classification) algorithms - fitting the parameters

My wish is to describe the time complexity of several classification approaches. For example, suppose we have $n$ data points in $m$ dimensional space and a binary class variable. We do not assume anything about its distribution (it may be symmetric or very skewed). In statistics, we choose a predictive model and fit its parameters. What is the time complexity of fitting

• naive Bayesian classifier
• logistic regression
• $k$-nearest neighbor classifier
• SVM
• $\ldots$

I understand that in some cases additional parameters or assumptions about the data (types of variables) are required. These parameters can be of course incorporated in your answer. Thank you very much!

## migrated from stats.stackexchange.comJan 12 '11 at 16:41

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

• Despite the statistical language used, this is purely a set of CS questions. You should be asking these questions and their counterparts (stats.stackexchange.com/q/6199/919 ) on a programming or algorithms site. When you migrate it (or it gets migrated for you), bear in mind that good practice is to ask one question at time, not an open-ended list of questions. – whuber Jan 12 '11 at 16:30
• It seems a bit broad since there are different ways of fitting those classifiers, with different complexities. For instance, one method for SVM is linear in the number of non-zero components, another one is quadratic in the number of examples, but there are dozens of others – Yaroslav Bulatov Jan 12 '11 at 20:15

"Training" a naive bayes classifier, assuming you're given the feature vectors, is $O(n)$, where $n = \sum_i nnz(x_i)$, where $nnz(x_i)$ is the number of nonzero features in data point $i$.
For the $k$-nearest neighbor classifier there is no training, but classifying has a high cost, and depends on the search algorithm you're using. For linear search the complexity is (for fixed k) proportional to the size of the training set for each point you want to classify. With approximate algorithms this can be brought down considerably at the expense of accuracy.
For svms standard quadratic-programming solvers are $n^3$, but recent approaches are inverse in the size of the training set. More information in this quora answer.