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$
2
  • $\begingroup$ O(log log n) ⊊ O(n) $\endgroup$
    – Raphael
    Oct 11, 2017 at 21:22
  • 2
    $\begingroup$ You may want to try a structured approach. $\endgroup$
    – Raphael
    Oct 11, 2017 at 21:23

1 Answer 1

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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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