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)


closed as unclear what you're asking by Matthew Drury, Michael Chernick, Dougal, Peter Flom Mar 30 '17 at 10:56

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ It is mathematical notation for terms that go to 0 almost surely. $\endgroup$ – Michael Chernick Mar 29 '17 at 23:33
  • 2
    $\begingroup$ Theres no way for us to ascess the correctness of your fomulas, as you did not define n, m, or M. Im currently voting to close as unclear, please edit in a definition of your terms. $\endgroup$ – Matthew Drury Mar 30 '17 at 0:11

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$.


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