patternMinor
What is the meaning of uniform distribution of elements in an array?
Viewed 0 times
meaningthewhatelementsarrayuniformdistribution
Problem
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?
Solution
Suppose that the array $A$ is chosen in the following way:
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.
- 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$.
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.
Context
StackExchange Computer Science Q#112782, answer score: 2
Revisions (0)
No revisions yet.