0

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.
Tim
  • 108,699
  • 20
  • 212
  • 390
thbrain
  • 1
  • 1
    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 https://stats.meta.stackexchange.com/questions/12/how-should-we-deal-with-obvious-homework-questions – Igor F. Jan 12 '21 at 08:00

1 Answers1

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.
Tim
  • 108,699
  • 20
  • 212
  • 390