Complexity of Search Algorithm

Question

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

• Raphael: O(log log n) ⊊ O(n)
• Raphael: You may want to try a structured approach.

Answer 1

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.