Supervised Machine learning classifiers big-O I'm comparing different machine learning for classifying sensor data and I need their complexity to select the most efficient. Which are the Big-O notation for the following algorithms (I add what I found):


*

*SVM (linear and all vs rest)- O(n^3)

*Random Forest (CART) - O (M(mn logn)) M-number of trees m-number of attributes and n-number of samples.

*Linear Discriminative Analysis (Fisher's) - O(2^n)

*Multilayer perceptron (learning-backpropagation and classification feed-forward)


Are they correct? Any source to find their Big-O notation?
I'm asking: 1) Are the Big O notation correct? 2) If not, which are the correct? (approximated)
 A: It's important to make a distinction between models and algorithms. Your list includes a mixture of the two. For instance, SVM is a model not an algorithm. There are different methods for finding an approximate solution to the SVM objective function (i.e. model fitting), and they generally have different complexities.
Modern approaches to fitting models are iterative optimization algorithms that converge to a solution in the limit. The per iteration Big-O complexity is a definite quantity, however the total running time depends on the number of iterations required to reach some specified measure of convergence, and this number of iterations depends on properties of the problem instance that are (usually) not easily measured.
As an example, linear SVM is usually fitted using stochastic gradient descent, which takes $O(nm)$ time for n data points and m features, per epoch. The number of epoches requires to reach a good solution depends on the problem but is typically small and unrelated to $n$ and $m$.
