2
$\begingroup$

I have algorithm that finds if there are two elements in sorted array that have sum zero.

1.ZeroSumPair(A[1..n]) // A[1..n] <-- sorted
2.    l <- 1, r <- n
3.    while(l < r)
4.        while(l < r or A[l] + A[r] > 0)
5.            r--
6.        if(A[l] + A[r] = 0)
7.            return true
8.        l++
9.    return false

Intuitively I know that this algorithm is $O(n)$, but how do I deduct it using proof with summations like in CLRS book?

I've also saw How to develop an $O(N)$ algorithm solve the 2-sum problem?, but I didn't see any formal proof.

$\endgroup$
  • $\begingroup$ I would try putting in a counter t. Then increment t 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 at 18:28
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I see that this looks formal but I feel like it is “hacking”, amending the algorithm in order to prove its complexity, is this real thing in computer science? Not talking about practice here $\endgroup$ – kuskmen Mar 27 at 21:53
  • 1
    $\begingroup$ @kuskmen you don't need $t$ explicitly in your code. I put it there for clarity. You can have an implicit "operation count" which is realistically what you're trying to determine. Then prove (through loop invariants) that the "operation count" is bounded by $n$. That's all I did here with $t$ being the operation counter. $\endgroup$ – ryan Mar 27 at 22:49
  • $\begingroup$ I see, I have to admit I am bad in mathematical proofs or any sort of proofs as you can tell. Can you tell why $t=t'+ 4 + 2k$ in the inductive step? $\endgroup$ – kuskmen Mar 28 at 8:15
  • 1
    $\begingroup$ Assume $t$ starts at $t'$ just before the loop executes. Now hop into the loop. Increment by 1 for the initial inner while loop check (line 5). Now assume the inner while loop executes $k$ times. There are 2 increments in the inner while loop (line 7 and line 9), so $t$ is then incremented $2k$ times. Next, exit the inner while loop, increment by 1 for the if comparison (line 10). Assume the if condition is false because we do worst case analysis, then increment by 1 for incrementing l (line 13). Increment 1 last time for the following while check (line 15). Add them all up and you get that. $\endgroup$ – ryan Mar 28 at 16:11
  • 1
    $\begingroup$ @kuskmen, this may also help you: cs.stackexchange.com/a/23595/68251 $\endgroup$ – ryan Mar 28 at 17:45

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.