Consider this slightly modified algorithm where I've added an "operation counter" t
. This will be incremented every time we do a comparison or assignment.
1. ZeroSumPair(A[1..n]) // A[1..n] <-- sorted
2. l <- 1, r <- n
3. t <- 3 // 2 for first two assignments and 1 for initial while check
4. while(l < r)
5. t++ // 1 for initial while check
6. while(l < r or A[l] + A[r] > 0)
7. t++ // 1 for decrementing r
8. r--
9. t++ // 1 for following while check
10. t++ // 1 for if comparison
11. if(A[l] + A[r] = 0)
12. return true
13. t++ // 1 for incrementing l
14. l++
15. t++ // 1 for following while check
16. return false
This is a bit verbose, but it will work. Now we must simply prove that, at termination we have $t = O(n)$. We can do this inductively with a loop invariant.
Let's use the following loop invariant for the loop on line 4.
$$t = 3 + 4(l-1) + 2(n-r)$$
Base Case
Initially $t = 3$, $l = 1$, and $r = n$. Thus we have:
$$3 = 3 + 4(1 - 1) + 2(n - n) = 3$$
Inductive Case
Let $t'$, $l'$, and $r'$ be the values of $t$, $l$, and $r$ at the end of our previous iteration. At the end of our current iteration we have $l = l' + 1$, $r = r' - k$ for some $k$, and $t = t' + 4 + 2k$. Thus we have:
$$\begin{align*}
t & = t' + 4 + 2k\\
& = 3 + 4(l' - 1) + 2(n - r') + 4 + 2k\\
& = 3 + 4(l - 2) + 2(n - (r + k)) + 4 + 2k\\
& = 3 + 4(l - 1) - 4 + 2(n - r) - 2k + 4 + 2k\\
& = 3 + 4(l - 1) + 2(n - r) & \square
\end{align*}$$
Thus, we can conclude the loop invariant holds. At the end of the loop (in the worst case) we have $l = r \leq n$. We then have:
$$\begin{align*}
t & = 3 + 4(l - 1) + 2(n - r)\\
& = 3 + 4l - 4 + 2n - 2l\\
& = 2(n + l) - 1\\
& \leq 2(n + n) - 1\\
& = 4n - 1\\
& = O(n) & \square
\end{align*}$$
Thus it is linear. There might be an easier way to do this, but this way makes sense to me pretty clearly.
t
. Then incrementt
by 1 every time you do an operation. Then try to prove a loop invariant for the outer-while loop that claims $t = O(n)$. With the correct loop invariant on $t$, this can be proven by induction relatively easily. Perhaps something like $t \leq c(l + (n - r))$ for some constant $c$ might work. Then at termination (in the worst case) you know $l = r$, thus $t \leq cn \implies t = O(n)$. $\endgroup$ – ryan Mar 27 '19 at 18:28