SVM prediction time increase with number of test cases I am using scikit-learn's SVM for the MNIST digit classification dataset. In order to improve the performance I extended the dataset by adding rotated samples. I was aware that SVM takes O(N^3) time to train the data, where N is the number of training vectors. 

However even prediction seems to take increase polynomially, the number of test vectors is the same. Is there any explanation for this or some equation that relates prediction time to the number of training samples?

I am using a 3rd degree polynomial as the kernel with C=100.0.

Note: I am doing a group project to compare the performance of various methods so I can't use any other method as my teammates would have used those. I referred to a paper by Decoste and Scholkoph which uses Virtual SVM. However I don't think I can run this on my current system if I can't run a simple extended training set.
The number of support vectors must be increasing. The prediction time is proportional to that; after all, the kernel classifier is $f(x) = \sum_i \alpha_i k(x, x_i)$, where the summation is over the support vectors. With sklearn you can find out how many you have by inspecting n_support_