2
$\begingroup$

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;
}
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.