# What does big O mean in KNN optimal weights?

Wiki gives this definition of KNN

In pattern recognition, the k-nearest neighbors algorithm (k-NN) is a non-parametric method used for classification and regression. In both cases, the input consists of the k closest training examples in the feature space. The output depends on whether k-NN is used for classification or regression:

• In k-NN classification, the output is a class membership. An object is classified by a plurality vote of its neighbors, with the object
being assigned to the class most common among its k nearest neighbors (k is a positive integer, typically small). If k = 1, then the object is simply assigned to the class of that single nearest neighbor.
• In k-NN regression, the output is the property value for the object. This value is the average of the values of k nearest neighbors.

k-NN is a type of instance-based learning, or lazy learning, where the function is only approximated locally and all computation is deferred until classification.

Both for classification and regression, a useful technique can be to assign weights to the contributions of the neighbors, so that the nearer neighbors contribute more to the average than the more distant ones. For example, a common weighting scheme consists in giving each neighbor a weight of 1/d, where d is the distance to the neighbor.

and this explanation about "The weighted nearest neighbour classifier"

The k-nearest neighbour classifier can be viewed as assigning the k nearest neighbours a weight 1/k and all others 0 weight. This can be generalised to weighted nearest neighbour classifiers. That is, where the ith nearest neighbour is assigned a weight $${\displaystyle > w_{ni}}$$, with $$\sum _{i=1}^{n}w_{ni}=1}$$. An analogous result on the strong consistency of weighted nearest neighbour classifiers also holds.

Let $$C_{n}^{wnn}$$ denote the weighted nearest classifier with weights $$\{w_{{ni}}\}_{{i=1}}^{n}$$.

Subject to regularity conditions on the class distributions the excess risk has the following asymptotic expansion $${\mathcal {R}}_{{\mathcal {R}}}(C_{{n}}^{{wnn}})-{\mathcal {R}}_{{{\mathcal {R}}}}(C^{{Bayes}})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},$$

and this formula

With optimal weights the dominant term in the asymptotic expansion of the excess risk is $${\mathcal {O}}(n^{{-{\frac 4{d+4}}}})$$

Does $$\mathcal {O}$$ here mean the Big O notation or something else?