For example, suppose you train a linear regression model using the Normal Equation, on a training set $\mathbf{X}$ containing $m$ instances and $n$ features. The Normal Equation requires computing $(\mathbf{X}^t \cdot \mathbf{X})^{-1}$, which is the inverse of an $n \times n$ matrix. According to the Wikipedia, inverting a matrix has a computational complexity of about $O(n^{2.4})$ using the best algorithms. On the other hand, the algorithm is linear with regards to the number of training examples $m$. So overall, it should be possible to train a linear regression model in $O(m \cdot n^{2.4})$.

Is there a table providing similar information for other Machine Learning algorithms, such as SVMs, Neural Networks (with $u$ layers and $v$ neurons per layer), Random Forests, KNN, Naive Bayes, etc.?


1 Answer 1


I was looking for the same table, which I never found. I ended up writing this blog post about time complexity of machine learning algorithms, where I focused on the most common algorithms (random forests, regressions, SVMs, kNN...).

It turns out that theoretical arguments such as yours and complexity evaluated on some implementations of some models can be quite different (sometimes due to default parameters, or to the different solvers that are being used).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.