how do you calculate nearest neighbor calculation times

Question

I have this question:

Suppose you are creating a website to help shoppers pick houses. Every time a user of your website visits the webpage for a specific house, you want to compute a prediction of the house value. You are using 1-NN to make the prediction and have 100,000 houses in the dataset, with each house having 100 features. Computing the distance between two houses using all the features takes about 10 microseconds. Assuming the cost of all other operations involved (e.g., fetching data, etc.) is negligible, about how long will it take to make a prediction using the brute-force method?

can somebody help me the formula?

Answer 1

For 1-NN, the complexity is O(N) per 1-NN query. Now, number of observations = 100,000 Time taken for calculating distance between two observations(t) = 10 microsecs Hence, for each feature, time taken = Nxt

Finally, for 100 features, the time taken will be = Nxtx100 = 1 second

Hope it helps