I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can someone please explain me this?
Suppose that the array $A$ is chosen in the following way:
- Sample $n$ real numbers uniformly from the interval $[0,1]$.
- Sort the $n$ samples.
Suppose that you choose a further uniform random variable $x$ from the interval $[0,1]$. The expected running time of interpolation search on $A$ and $x$ is $O(\log\log n)$, where the expectation is over the choices of both $A$ and $x$.
Usually an array is considered as uniformly distributed when the difference between the elements are equal or almost same. Example 1: 1,2,3,4,5,6 (Difference is 1)
Example 2: 10,20,31,40,55,60,73,80(Here the difference between the two adjacent elements are almost close to 10).
Interpolation search is to be used when the given array is both sorted and uniformly distributed to have log(log n) time complexity.