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 &lt; end) {
      int tempSum = elements[start] + elements[end];
      if (tempSum == sum) return true;
      if (tempSum &gt; 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.