Interpolation Search

Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys.

An improvement on Binary Search. Recall the run-times in a sorted array using binary search:

• insert, delete: $\Theta (n)$
• search: $\Theta (\log n)$

Best-case covered but not expected case

See tutorials, also $O(\log \log n)$ for average but why?

Works nicely when keys are evenly distributed (uniformly distributed), not as good when they are not. The best distribution would be increased linearly.

Motivation

$Interpolation-search(A[l,r],k)$: Compare at index $l+\lfloor \frac{k-A[l]}{A[r]-A[l]}(r-l)\rfloor$

Works well if keys are uniformly distributed:

• Recurrence relation is $T^{avg}(n)=T^{avg}(\sqrt{n}+\Theta (1))$
• Resolves to $T^{avg}(n)\in \Theta (\log \log n)$ for average case runtime of interpolation search!
• We have not seen expected runtime
• Best-case runtime is covered in tutorials: Go fetch it!

Questions

It is not possible for a comparison-based searching algorithm to terminate in $o(\log n)$ time.

• False , why?
• The notation $o(\log n)$ represents a time complexity that is strictly smaller than $\log n$. It means that the algorithm runs in sub-logarithmic time, implying a faster runtime than logarithmic time. It is possible for a comparison-based searching algorithm to terminate in sub-logarithmic time. For example, if the elements are already sorted, a binary search algorithm can locate the desired element in $\log n$ time. This time complexity is better than $o(\log n)$, but it still falls within the category of comparison-based searching algorithms.

Consider an algorithm that runs both Binary Search and Interpolation Search simultaneously until one of them stops. The worst-case runtime will be bounded by $O(\log n)$ and if the keys are uniformly distributed we would expect a runtime of $\Theta (\log \log n)$.

• True, why??