# KNN Complexity (Big O notation)

I need to show the Big O Notation for KNN algorithm. So I wanted to know

1. the complexity of brute force KNN algorithm; and
2. to make the graph do we have x-axis: input size, y-axis: the speed.
• Is this a self-study question? If yes, please add the corresponding tag and edit your question to show what you've tried so far and where you got stuck. See also stats.meta.stackexchange.com/questions/12/… Commented Jan 12, 2021 at 8:00

• Next, you need to write down what steps the $$k$$-NN algorithm does. For example, if it needs to run a for loop, than the loop alone is $$O(n)$$ since you need to do something for each of the $$n$$ cases. All the other steps would increase the complexity. If you want a spoiler, here's an exact answer about $$k$$-NN.
• If you want to plot the Big O thing, treat the stuff inside $$O(\cdot)$$ as a regular function and plot it. Same rules apply as about plotting any other function, so for example if there are multiple dimensions, e.g. $$O(mn)$$, i.e. the complexity depends on the number of rows $$n$$ and columns $$m$$, you would either need a 3D plot, or make some choices on what and how to show otherwise.