2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

Suppose that the array $A$ is chosen in the following way:

  1. Sample $n$ real numbers uniformly from the interval $[0,1]$.
  2. 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$.

In fact, if I understand Gonnet's thesis correctly, the expectation is still $O(\log\log n)$ even for any fixed $x$. See also Gonnet et al.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This isn’t the meaning in this case, however. $\endgroup$ – Yuval Filmus Oct 4 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.