If I have a support vector machine which has already been trained, what is the computational complexity of classifying a new example using that machine? I care about both time and space complexity.
Does the answer change if the underlying metric space is unusual -- for instance, Damerau-Levenshtein edit distance (computing which is $O(n^2)$ time and space for strings of equal length) instead of Euclidean ($O(n)$ time and $O(1)$ space)?
(This is related to Computational complexity of learning (classification) algorithms - fitting the parameters but that's about the training process.)
(Edit: the paper that sparked this question is http://www.cs.stonybrook.edu/~xcai/fp.pdf )