What is the time complexity of interpolation search when the input array has uniformly distributed values and is sorted?
(a) O(n)
(b) O(log log n)
(c) O(n log n)
(d) O(log n)
I had been asked this question in an international level competition.
I'm obligated to ask this question of Searching topic in chapter Searching of Data Structures & Algorithms II