The Performance of Interpolation Search

If the data is unevenly distributed, the performance of the interpolation search algorithm will be poor. The worst-case performance of this algorithm is O(N) and if the data is somewhat reasonably uniform, the best performance is O(log(log N)).