Is it known what is the LIBSVM time complexity when using RBF kernel functions?
The training complexity for nonlinear kernels is roughly between $O(n^2)$ and $O(n^3)$ where n is the number of training data points.
If you are using scikit-learn's implementation of LIBSVM the documentation claims (http://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html):
The fit time complexity is more than quadratic with the number of samples which makes it hard to scale to dataset with more than a couple of 10000 samples.
A reference you can use is: http://colt2009.cs.mcgill.ca/papers/021.pdf
Also, the LIBSVM reference which explains the computational complexity can be found in section 4.3 of: http://fbim.fh-regensburg.de/~saj39122/Diplomarbeiten/Miklos/SVM%20Toolboxes/libsvm.pdf