KNN’s runtime

KNN’s runtime

Evangeline is working with a dataset with a single column of data.

She wants to run k-Nearest Neighbors (KNN), but only if the algorithm is fast enough when making predictions.

Assuming there are n samples in the dataset, which of the following will be the runtime of Evangeline’s KNN at prediction time?

1. The runtime that Evangeline should expect is O(1)

2. The runtime that Evangeline should expect is O(n)

3. The runtime that Evangeline should expect is O(log n)

4. The runtime that Evangeline should expect is O(n²)

Attempt

k-Nearest Neighbors’ runtime is O(nd) because we need to compute the distance to each feature of every sample. Here n represents the number of instances, and d the number of features.

Evangeline is working with a single feature, so d = 1. Therefore, in this case, the runtime of KNN is O(n).

Recommended reading

Here is a Stack Exchange answer that covers KNN’s runtime complexity in detail.