Interpolation Search

Learned in CS240.

Go through Module 6 of CS240 is you want to see an example of the algorithm being applied.

Works well if keys are uniformly distributed: Can show: Recurrence relation is $T^{(avg)}(n)=T^{(avg)}(\surd n)+\Theta (1)$ This resolves to $T^{(avg)}(n)\in \Theta (\log \log n)$

However, the worst case performance is $\Theta (n)$.