I have an algorithm which searches a sorted int array for two elements which sum up to a searched value. First I thought that the complexity is $\mathcal{O}(n)$, but the interpolation search algorithm has a similar approach and has a $\mathcal{O}(\log(log(n)))$ complexity with uniform distributed elements.
Which is the right complexity and why?
boolean hasPairWithSum(int[] elements, int sum) {
int start = 0;
int end = elements.length-1;
while (start < end) {
int tempSum = elements[start] + elements[end];
if (tempSum == sum) return true;
if (tempSum > sum) {
end--;
} else {
start++;
}
}
return false;
}