My doubt is about the grow of the training data using K-NNs and Naive Bayes. As it grows larger, does prediction (on test data) become also computationally harder?
Here is a good Intro to KNN. And from its algorithm its clear that more the number of samples or data, more the number of computations required. Here the computations are usually the Euclidean distance between the predicting data point and all the labeled samples.