Why is KNN so much faster than decision tree?

Question

Once in an interview I came across a question from an employer. He asked me why the KNN classifier is much faster than the decision tree, for example, when recognizing letters or recognizing faces?

At that time, I had no idea. So, I want to know in what terms should I compare the two classification methods in performance? Thanks.

Answer 1

Consider the following data set: N samples, each of which has attributes k. Generally:
1. naive KNN: O (1) [training time] + O (NK) [request time] = O (NK)
2. The naive decision tree: O (N ^ 2 * K * log (N)) [training time] + O (log (N)) [query Time] = O (N ^ 2 * K) - also for query time, we assume that the tree is balanced.
To calculate the complexity, I looked at a very simple implementation of each classifier. There are already several improvements for implementing KNN and the decision tree.