Search code examples
algorithmmachine-learningdecision-treeknn

Why is KNN much faster than decision tree?

Once in an interview, I encountered a question from the employer. He asked me why KNN classifier is much faster than decision tree for example in letter recognition or in face recognition?

I had completely no idea at that time. So I want to know in which terms should I compare the two classification methods in speed performance? Thanks.

Solution

  • Consider the following dataset: N samples, each has k attributes. In general :
    1. naive KNN: O(1) [training Time] + O(NK) [query Time] = O (NK)
    2. 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 complexities, I considered very simple implementation of each classifier. Already there are few improvements for implementing KNN and Decision Tree.