What is the time complexity of interpolation search when the input array has uniformly distributed values and is sorted?
(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