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.
  • 1
    $\begingroup$ 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/… $\endgroup$
    – Igor F.
    Commented Jan 12, 2021 at 8:00

1 Answer 1


This seems to be a question, so let me give you few hints.

  • Start with refreshing your knowledge on Big O notation, e.g. you can check Wikipedia, this StackOverflow.com answer, or many one of many online tutorials like this.
  • 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.
  • As about graphs, from practical point of view, the most useful thing you can do to produce them, is to actually run the algorithm for different input sizes and record the runtime, to plot it later. This would help you to verify if your theoretical calculations agree with the actual results.
  • 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.