Nearest Neighbour
Problem Description
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.
Bounds Chart
Step Chart
Improvement Table
Complexity Classes  Algorithm Paper Links  Lower Bounds Paper Links 

Exp/Factorial  
Polynomial > 3  
Cubic  
Quadratic  [Linear search (1940)]  
nlogn  kd Tree (1975)  
Linear  Projected radial search (2013)
[Compression/Clustering Vector Quantization (1992)] 

logn 