We all know the k-means clustering algorithm and the k-nearest neighbors algorithm: the former is an unsupervised clustering method, and the latter is a supervised learning technique in machine learning.
We all know that they both are simple algorithms, and we can explain easily how they work.
Even though most of people in machine learning consider them simple algorithms, why are they simple algorithms? What are the scientific reasons that make them simple? How to define simplicity in machine learning algorithms?
Best Answer
You can put some numbers to answering this question. In general, k-means and kNN are fairly old algorithms, which may be one of the reasons for this.
For k-means, I reference you to Complexity
and this paper Time Complexity of K-Means and K-Medians Clustering Algorithms in Outliers Detection. There is als a more friendly post The Cost Function of K-Means
Vanilla kNN, for large data sets, has a large computational cost. There is an old post on kNN complexity: k-NN computational complexity
You can then compare that with something like recurrent Neural Networks. Here is a paper on the complexity analysis Bounds on the complexity of recurrent neural network implementations of finite state machines