# Compute Time Complexity of Neural network, SVM and other classification algorithms

I would like to know what is the asymptotic time complexity analysis for general models of Back-propagation Neural Network, SVM and Maximum Entropy. Does it just depend on number of features included and training time complexity is the only stuff that really matters.

And does it real matter when applying on large chunk of text classification like twitter data or blog data

• SVMs contain an underlying optimization step that is solved heuristically, so for any actual algorithm that purports to solve SVMs, the answer is undefined. A number like $O(n^3)$ is generally bandied around for implementations like libsvm, which means something like time/iteration * #iterations (where #iterations is assumed to be constant) – Suresh Venkat Aug 25 '13 at 17:50
• @SureshVenkat: That should be an answer, not a comment. – Jeffε Aug 31 '13 at 18:14
• @JɛﬀE it is done. – Suresh Venkat Sep 1 '13 at 5:17

SVMs contain an underlying optimization step that is solved heuristically, so for any actual algorithm that purports to solve SVMs, the answer is undefined. A number like $O(n^3)$ is generally bandied around for implementations like libsvm, which means something like time/iteration * #iterations (where #iterations is assumed to be constant)
Relevance Vector Machines need a $O(n^3)$ time too, but the main overhead there is in the learning phase, it needs to repeatedly compute the inverse of a Hessian Matrix (that requires $O(n^3)$ computations.
However, a preprocessing step is often useful and it also costs you $O(nd)$, specially if you want faster classification speeds. This is a good paper to read if you want to know more.