Question

Show that the average-case time complexity of Interpolation Search is in \(\Theta(\lg (\lg n)),\) assuming the keys are uniformly distributed and that search key \(x\) is equally probable to be in cach of the array slots.

Short answer

The average-case time complexity of Interpolation Search is in \( \Theta(\lg (\lg n)) \).

Step-by-step solution

Understanding the Interpolation Search Algorithm

Interpolation search is an improvement over Binary Search where mid is calculated using the formula \[ \text{{mid}} = \text{{lo}} + \frac{((\text{{key[hi]}} - \text{{key[lo]}}) * (hi - lo))}{(\text{{key[hi]}} - \text{{key[lo]}})} \] which leads to better position than the middle position of binary search for most of the cases particularly when the elements are uniformly distributed.

Formula for average case of Interpolation Search

The average case time complexity of the Interpolation Search can be defined as follows: For a successful search, the average time complexity can be logarithmic in the number of keys \( n \). It can be estimated that on average the Interpolation search algorithm makes about \[ \log_2\left(\log_2\left(\frac{n+1}{2}\right)\right) \] comparisons if the elements are uniformly distributed.

Proving the equation is in \( \Theta(\lg (\lg n)) \)

The Big Theta notation represents the average run-time complexity of an algorithm. When we say that the run-time complexity of interpolation search is \( \Theta(\lg (\lg n)) \), it means that the scaling of the interpolation search time on average scenario falls into this category. Considering the uniformly distributed keys and a key is equally probable in each slot of the array, our derived relation \[ \log_2\left(\log_2\left(\frac{n+1}{2}\right)\right) \] falls into \( \Theta(\lg (\lg n)) \). Thus, the average case time complexity of the Interpolation search is in \( \Theta(\lg (\lg n)) \).