The well-known classifiers that can be trained/tested in linear time I am interested in collecting the list of the classifiers that (depending on their setting) can have linear time complexity (both in training and testing step) with respect to the number of samples $n$, the number of features of each sample $m$, and the number of classes $c$.

In other words, I am seeking for a list of the well-known classifiers that can have the complexity of $\mathcal{O}(mnc)$ or lower.

1- I know that Naive Bayes classifiers are so; given that the parameters of the utilized probability distributions can be estimated in linear time (e.g. Poisson Naive Bayes and Multinomial Naive Bayes)

2- I also know that when K-NN is utilized as classifier (counting the K-nearest neighbors and choosing the most-voted class), it is also included in this list.

Although this list, in theory, can be extended infinitively, I am interested in completing the list by the well-known classifiers by the CS community.

I searched the web, a lot, but seemingly, there is no page even speaking about such subject or such list. The only thing that I found was a lot of info about "linear classifiers" whose scope is much more general than my question (even their list includes SVM and etc.).
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.