The complexity of training a SVM is discussed succintly in Section 4.2 of [1]. In particular, time complexity depends on both R^3 (where R is the number of free support vectors) and nS (where n is the number of training samples and S is the number of support vectors). Space complexity depends on how many training samples are stored at each iteration by your solver.

For running a SVM, space and time complexity are linear with respect to the number of support vectors.

Clearly, this discussion is independent of the computation of the kernel values which are assumed as given, and in some cases this can be the main bottleneck.

[1] Bottou, Léon, and Chih-Jen Lin. "Support vector machine solvers." Large scale kernel machines (2007): 301-320.

The complexity of training a SVM is discussed succintly in Section 4.2 of [1]. In particular, time complexity depends on both R^3 (where R is the number of free support vectors) and nS (where n is the number of training samples and S is the number of support vectors). Space complexity depends on how many training samples are stored at each iteration by your solver.

For running a SVM, space and time complexity are linear with respect to the number of support vectors.

Clearly, this discussion is independent of the computation of the kernel values which are assumed as given, and in some cases this can be the main bottleneck.

[1] Bottou, Léon, and Chih-Jen Lin. "Support vector machine solvers." Large scale kernel machines (2007): 301-320.

Training a SVM is a quadratic programming problem, how can it be NP-complete? It would be nice to see any publication claiming this.

"Olivier Chapelle" talks extensively about complexity of SVM in this paper. and find an optimization.  He made an arugument that as "Support Vector Machines

(SVMs) first state the primal optimization problem, and then go directly to the

dual formulation" and  one should solve either the primal or the dual optimization problem depending on whether n is larger or smaller than d, resulting in an O(max(n, d) min(n, d)^2) complexity. where

Given a matrix(dataset) X ∈ R^( n×d) representing the coordinates of n points in d dimensions

For details may refer to the paper please : http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/neco_%5b0%5d.pdf

About ANN: I am sorry, I didnt have enough knowledge. 

For ANN the time complexity : O(n^4) for Forward Propagation

:O(n^5) for Backward Propagation