It is completely normal in some circumstances. If you consider the learning problem from a statistical perspective, learning is done by trying to estimate the conditional estimate of your output variable given input variables. When you are doing learning you basically have to main components: sample data from training and the learning algorithm, and you use both to build an estimation of the aforementioned conditional probability. Now consider the relation of each component with the desired estimated probability.
Training data is only a sample from all the possible data. You do not have all the possible data since if you would have it you would not need to do learning, right? So a sample is just a fraction of the data. This sample could cover more or less the whole domain of the possible data. An immediate thought is that a bigger sample is better than a smaller one. As an extreme case to illustrate the idea is to have only one observation. But the size of the sample is not the whole story. It is possible that the probability you want to estimate is very complex. The complexity of that space requires also more data than a simple probability space. To give an example consider the problem of learning the mean of the heights of males from USA. Having a small random sample often would be enough if you assume a normal distribution. One the other hand take the example of learning to recognize speech. Since pronouncing is not the same against individuals you would need a pretty big sample to unveil the useful relation needed to predict and throw away things which are not useful in the data.
Not any model is appropriate to express any true model of the signal you learn. For example if your true signal resembles a second degree polynomial would be impossible to fit properly with a linear model, other than some particular cases. So there is a complexity in the model too, which could be compared with the complexity of the conditional probability you want to estimate during learning. Even if you know the true model and you learning model is able to describe it, sometimes you need more data to make the model able to fit. As another example consider a random forest which estimates a simple line. Random forest is very flexible since the underlying statistical model is basically a constant given a local region in the input space. Considering that, even if the model would be capable of estimating the true model, since the model is a local approximation, you need plenty of data in every useful region of the space, to learn a good approximation.
We considered the individual component comparisons with probability you want to estimate. But you have both. This makes even harder to understand what is happening behind the walls of learning. Thus there are no universal ways of telling when data is enough for a given model. So this is why is often the case that one algorithm can have different accuracies for different training set size and for different algorithms the required training set size to have approximate equal accuracies.
One thing I tried often in practice is given a learning model to check how accuracy evolves as the learning sample size increase. If your training sample is large enough you have typically a region in a small sample size where error is large due to not enough data. After that you would have a region where errors stays approximately the same and this perhaps is where your model do it's best. Also is possible for even larger sample sizes to have a decrease in performance for some models, maybe do to inability of the model to describe what is there or due to overfitting or some other cases.
You can trace this kind of behavior using some sort of bootstrap validation, where the sample used for training is taken repeatedly for increasing lengths. Something like 20 samples with 5% size, 20 samples with 10% size, and so on. This kind of information can give you an idea between the relation of the sample size with your learning problem for a given algorithm.