How do I describe formally complexity of 2-sum problem algorithm?
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] &lt;-- sorted
2.   l &lt;- 1, r &lt;- n
3.   t &lt;- 3             // 2 for first two assignments and 1 for initial while check
4.   while(l &lt; r)
5.     t++              // 1 for initial while check
6.     while(l &lt; r or A[l] + A[r] &gt; 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 &amp; = t' + 4 + 2k\\
  &amp; = 3 + 4(l' - 1) + 2(n - r') + 4 + 2k\\
  &amp; = 3 + 4(l - 2) + 2(n - (r + k)) + 4 + 2k\\
  &amp; = 3 + 4(l - 1) - 4 + 2(n - r) - 2k + 4 + 2k\\
  &amp; = 3 + 4(l - 1) + 2(n - r) &amp; \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 &amp; = 3 + 4(l - 1) + 2(n - r)\\
  &amp; = 3 + 4l - 4 + 2n - 2l\\
  &amp; = 2(n + l) - 1\\
  &amp; \leq 2(n + n) - 1\\
  &amp; = 4n - 1\\
  &amp; = O(n) &amp; \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.