Exactly Vinay. But to make the search for n neighbors fast you could use data structure like KD-tree/ ball tree which requires O(kn log n). If you look at the documentation of Sklearn, it uses the ball tree (by default). Nevertheless, it has been mistakenly mentioned in the post that the train time complexity of KNN is O(knd).