from edurev

Question

Consider an interpolation search which is an improvement over binary search where the values in a sorted array are uniformly distributed.In interpolation search construction  of new data points take place at different location according to the value of the key being searched.Find the time complexity of interpolation search.

A.O(logn)

B.O(n)

C.O(n logn)

D.O(log(logn))

Please explain by taking an example

Answer 1

Answer is D. log(log(n))

Explanation : Interpolation search may go to different locations according to the value of the key being searched.

The index position in the array from where the search will start will calculated by given formula:

pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

arr[] ==> Array where elements need to be searched
x     ==> Element to be searched
lo    ==> Starting index in arr[]
hi    ==> Ending index in arr[]

Example :

Let us consider an sorted array > arr[] =  {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};

and element to be search is 19

pos = 0 + [(19 - 10)*(14 - 0)/(47 - 10)]

pos = 3.4, will take as 3

so, we start from index 3 not from middle element (as in case of binary search)

arr[3] < 19, which means element will be at higher index positions.

 

 

Answer 2

O(log(log(n)))