K Nearest Neighbour is a simple algorithm that stores all the available cases and classifies the new data or case based on a similarity measure. It is mostly used to classifies a data point based on how its neighbours are classified.
|Complexity Classes||Algorithm Paper Links||Lower Bounds Paper Links|
|Polynomial > 3|
|Quadratic||[Linear search (1940)]|
|nlogn||k-d Tree (1975)|
|Linear||Projected radial search (2013)
[Compression/Clustering Vector Quantization (1992)]