Can this algorithm run in O(n) time?

Question

I am writing an algorithm to figure out if there is a pair of integers in a sorted array sum to a given integer. I want the algorithm to run in O(n) where n is the number of integers in the subarray.

The input are bounds of subarray and integer to test the sum on. The output would be a boolean.

Here is my algorithm. k is the given integer, i and j are the bounds of the subarray.

kPairSumInterval(int k, int i, int j)
         if(i == (j-1))
              sum = A[i] + A[j]
              if(sum == k)
                 found = true;

         kPairSumInterval(k,i+1,j)
         for j down to i
              sum = A[i] + A[j]
              if(sum == k)
                  found = true

        return found

Is the while loop going to affect the running time or do we just focus on the number of stack frames the recursion does ? If the algorithm won't run in O(n) time, I would appreciate some suggestions to make it run in O(n).

What is the sense of `k` and `j` passed as arguments, if they are constant? — Yeldar Kurmangaliyev, Oct 28 '15 at 05:19
@YeldarKurmangaliyev I don't know. The instructor wants the method to be implemented like this. There is another method that takes k as argument and calls kPairSumInterval. I don't think it matters. — Altaïr, Oct 28 '15 at 05:22
Are the lists sorted? Is the first sum supposed to read `sum = A[i] + A[j]` — AChampion, Oct 28 '15 at 05:27
@AChampion Yeah sorry I corrected it and yes the list is sorted. — Altaïr, Oct 28 '15 at 05:28
No, this algorithm doesn't run in O(n) and you cannot make it run in O(n). No, you cannot ignore the while loop. — n. m. could be an AI, Oct 28 '15 at 05:36
Can you give my suggestions on how to design an algorithm that runs in O(n) ? — Altaïr, Oct 28 '15 at 05:37
Possible duplicate of [Linear time algorithm for 2-SUM](http://stackoverflow.com/questions/11928091/linear-time-algorithm-for-2-sum) — Sinkingpoint, Oct 28 '15 at 05:38
@Quirliom I want to write a recursive version. That is different. — Altaïr, Oct 28 '15 at 05:43
@Altaïr Fundamentally, a recursive solution would be polynomial at best. — Sinkingpoint, Oct 28 '15 at 05:44
No, it's not different. If you understand the mathematical idea behind the algorithm then you should have no problem to express it either recursively or iteratively. — n. m. could be an AI, Oct 28 '15 at 05:54

AChampion · Accepted Answer · 2015-10-28T13:46:24.843

Simple enough algorithm for a sorted list.
Assuming all positive integers, set an index to the end of list and an index to the beginning of the list and depending on the sum decrement the end index or increment the start index.
Python pseudocode:

def kPairSumInterval(k, i, j):
    x, y = i, j-1
    while x < y and A[x] + A[y] != k:
        if A[x] + A[y] > k:
            y -= 1
        else:
            x += 1
    return x < y

Just for demonstration purposes same algorithm recursively, using boolean arithmetic, i.e. True==1 and False==0:

def kPairSumInterval(k, i, j):
    if i >= j-1:
        return False
    result = A[i] + A[j-1]
    if result == k:
        return True
    return kPairSumInterval(k, i+(result < k), j-(result > k))

score 0 · Answer 2 · answered Oct 28 '15 at 05:58

0

You can use 2 pointers

start one from index 0 and 2nd from index n-1
check the sum if it is less than desired sum increase the front pointer and check.
if It is less, decrease the back pointer and check.
Termination condition would be pointer crossing each other.

Algo

desired_vale;
sum=0;
int p1,p2;
sortedArray[n];
p1=0;
p2=n-1;
for(;p1<p2;) // since you need pair = not required
{
sum = sortedArray[p1] + sortedArray[p2];
if(sum==desired_vale)
  return true ; //pair exist
else if (sum < desired_vale)
   p1++;
else
   p2-- ; 
}
return false; // could not find pair

The catch here is the sorted array, hence it can be done in order of log(n) by the given approach.

answered Oct 28 '15 at 05:58

Satyam Naolekar

560
7
10

This algorithm appears to be O(n) to me. Consider a source containing all even numbers from `2` to `n`, and a desired sum of `n+1`. You end up testing `n-1` sums before you discover the desired sum is not present. – Steven Hansen Oct 28 '15 at 06:11
yes you are correct, I have not applied optimizations to detect if sum is present or not, but this algo has upper bound of o(n) – Satyam Naolekar Oct 28 '15 at 08:18

score 0 · Answer 3 · answered Oct 28 '15 at 06:07

Recursive version of well known two-pointers algorithm (Delphi). Linear complexity.

function FindSum(const A: array of Integer; Sum, l, r: Integer): Boolean;
var
  s: Integer;
begin
  if l >= r then
    Result := False
  else  begin
    s := A[l] + A[r];
    if s = Sum then
      Result := True
    else if s > Sum then
      Result := FindSum(A, Sum, l, r - 1)
    else
      Result := FindSum(A, Sum, l + 1, r)
  end;
end;

Can this algorithm run in O(n) time?

3 Answers3