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).