For what it's worth, I don't think it's fair to claim that SVM is O(n^3). From [1], LibLinear trains linear SVMs in O(nd log (1/p)) time, where n is the number

For what it's worth, I don't think it's fair to claim that SVM is O(n^3). From [1], LibLinear trains linear SVMs in O(nd log (1/p)) time, where n is the number of examples, d is the number of features, and p is the optimization tolerance, and Pegasos/FOLOS and other subgradient methods can do online kernel SVM training in O(s / λ p) iterations, where s is the number of non-zero features in each example, p is as above, and λ is the regularization parameter. There are also lots of ways to speed up decision tree training from the naive approach - I explain/implement some in [2] (and in the Go decision tree library I worked on [3]), and there are many more (bucketizing, presorting, etc). The bound I've seen is O(mn log m + mnT) with T rounds, m examples, and n features. [1]: http://cseweb.ucsd.edu/~akmenon/ResearchExam.pdf http://cseweb.ucsd.edu/~akmenon/ResearchExam.pdf [2]: http://tullo.ch/articles/speeding-up-decision-tree-training/ http://tullo.ch/articles/speeding-up-decision-tree-training/ [3]: https://github.com/ajtulloch/decisiontrees https://github.com/ajtulloch/decisiontrees