The well-known classifiers that can be trained/tested in linear time
You might want to read my blog post Comparing Classifiers, especially the MNIST summary.

Time Complexity of Training

By Training Samples

Let $n$ be the number of training samples.

The following classifiers can perform at least on training / fitting step in $\mathcal{O}(n)$:


Neural Networks: You can take a fixed batch size. Then increasing $n$ is simply having more mini-batches to train on.
$k$-nearest-neighbors: All "training steps"


The following classifiers cannot perform at least one training / fitting step in $\mathcal{O}(n)$:


???


I am unsure about the following:


SVMs
Decision Trees: I'm relatively sure it is linear, but I would need to go through one of the training algorithms


By classes

If $n$ is the number of classes, then the training of $k$-NN is in $\mathcal{O}(1)$. If you keep the number of samples and k constant, then it doesn't matter if you have 2 classes or $10^{100}$.

I'm unsure about:


Neural Networks: The size of the last layer grows. My intuition is that this is in $\mathcal{O}(n)$, but I need to put more thought into it. I am, however, not sure if the Big-O Time Complexity makes a lot of sense for this classifier. If you look at the tables in Appendix D, you see that in real problems the FLOPs are dominant in the beginning. Given a problem, you usually you can't influence the number of classes. And the wall-clock time complexity of training for two classes is vastly different for different classifiers. So much, that up to a reasonable amount of classes you will likely not see the asymptotic behavior.
Decision trees might even be in $\mathcal{O}(1)$. I have to give impurity measures a closer thought.