0
$\begingroup$

Assume $A$ is an array that contains sorted integers , ie $\forall\ i,j$ where $1 \le i \le j \le |A|$, $A_i \le A_j$. The numbers do not have to be unique, and the task is to check if there is at least one pair of indices $i$ and $j$ where $A_i + A_j = n$. Simple enough, here's an algorithm that does it:

CheckForPair(A, n, i, j):
    if i >= j or outOfBound:
        return false
    v := A[i] + A[j]
    if v = n:
        return true
    if v < n:
        return CheckForPair(A, n, i + 1, j)
    if v > n:
        return CheckForPair(A, n, i, j - 1)

CheckForPair(A, n):
    return ChcekForPair(A, n, 1, |A|)

Mathematically,

$$ \begin{align} CheckForPair(A, n, i, j) &= \begin{cases} false & \text{if $i \ge j$ or $i < 1$ or $j > |A|$,} \\ true & \text{if $A_i + A_j = n$,} \\ CheckForPair(A, n, i + 1, j) & \text{if $A_i + A_j < n$,} \\ CheckForPair(A, n, i, j - 1) & \text{if $A_i + A_j > n$} \\ \end{cases} \\ \\ CheckForPair(A, n) &= CheckForPair(A, n, 1, |A|) \end{align} $$

This is an algorithm I have seen somewhere else and I am trying to prove its correctness. For $i$ and $j$ that are on the very ends on the array (ie $i = 1$ and $j = |A|$), it's easy to see why it is correct since:

  • if $A_i$ + $A_j < n$, then $i$ must increase because $j$ cannot increase.
  • if $A_i$ + $A_j > n$, then $j$ must decrease because $i$ cannot decrease.

However, for $i$ and $j$ that are in between, I fail to see why the above still holds.

$\endgroup$
1
$\begingroup$

It is a recursive definition, thus we can use induction. Let me first rephrase the algorithm a bit:

$$ CFP(n,A) = \begin{cases} False& \text{if }A=[\;]\\ True& \text{if } first(A) + last(A) = n\\ CFP(n,tail(A))&\text{if }first(A)+last(A)<n \\ CFP(n,init(A))&\text{otherwise} \end{cases} $$ where $tail(A)$ means all of $A$ but the first entry, $init(A)$ means all of $A$ but the last entry and $first(A)$ and $last(A)$ mean the first and last elements of $A$ respectively.

We now prove the statement by induction on the length of the array:

  1. |A| = 0: $CFP (n,A)=False$ in accordance with the fact that there is no indices $i,j$ with $A_i+A_j=n$.
  2. We assume the algorithm is correct for arrays of length $n$: Let $A$ be an array with $|A|=n+1$. If no pair of indices $i\leq j$ with $A_i+A_j=n$ exists, then either $CFP(n,A) = CFP(n,tail(A))$ or $CFP(n,A)=CFP(n,init(A)$. By induction hypothesis, the algorithm returns the correct result in both cases. On the other hand, if a pair $i\leq j$ of indices with the desired property exists, we distinguish the following cases:
    • $A_i=first(A)$: In this case, $first(A)+last(A)\geq n$ (because of how $A$ is ordered). Thus the algorithm either returns $True$ or $CFP(n,init(A))$. In the latter case $j$ is not the last index of $A$, thus the correctness of the result follows from the induction hypothesis.
    • $A_j = last(A)$: Analog to the previous case.
    • $first(A)<A_i\leq A_j<last(A)$: either $CFP(n,tail(A))$ or $CFP(n,init(A)$ is called. Since the a the statement is true for both $init(A)$ and $tail(A)$, the algorithm will correctly return $True$ by induction hypothesis.
$\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.