# Complexity of Search Algorithm

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;
}


This method works in linear time, because end - start decreases by 1 on each iteration. It's $n - 1$ initially, hence the loop will make at most $n - 1$ iterations.