Using a Progress Measure

This is another trick that you might not have studied formally but have used (implicitly) before. This trick is generally used to bound the number of times a loop is executed in an algorithm.

Background

In this note, we will consider another trick that you might not have studied formally but have used (implicitly) before. This trick is generally used to bound the number of times a loop is executed in an algorithm. Since most non-trivial algorithms have loops in them, this is a useful trick to remember when trying to bound the run time of an algorithm (which you will have to do frequently in this course). Most of the time you will need to use the trivial version of this trick.

A simple example

Let us begin with a prototypical example that you have already seen. Consider the following simple problem:

Search Problem

Given $n+1$ numbers $a_1,\dots,a_n;v$, we should output $1\le i \le n$ if $a_i=v$ (if there are multiple such $i$'s then output any one of them) else output $-1$.

Below is a simple algorithm to solve this problem.

Linear Search Algorithm

                                // Input: A[i] for 0<= i<n
                                // Input: v

                                // Search
                                for(i=0; i< n; i++)
                                    if(A[i] == v)
                                        Return i;
                            
                                Return -1;

We will consider the run time analysis of this algorithm in the course but the main step is to compute an upper bound on the number of iterations of the loop in Step 5. In this case it is easy to come up with a bound of $n$: in each iteration of the loop, the value of i is incremented by $1$. i is initialized to a value of $0$ and the loop stops once i$\ge n$. This means i can be incremented at most $n$ times and since in each loop the value of $i$ is incremented, the loop can be iterated in at most $n$ times.

Trick: Bounding the Progress

One can generalize the above argument to bound the number of iterations of pretty much any loop we will encounter in this course. Here is general outline:

Trick

Define a notion of progress, i.e. after the $i$'th iteration of the loop, let $\mathcal{P}(i)$ denote a integer with the following properties:

  1. Argue that $\mathcal{P}(0)=\ell$ (here I am assuming that the loop starts with $i=0$);
  2. Argue that $\mathcal{P}(i+1)>\mathcal{P}(i)$ for every $i\ge 0$;
  3. Argue that for every $i\ge 0$, $\mathcal{P}(i)\le u$.
  4. Conclude that the number of iterations is bounded by $u-\ell+1$.

As an exercise, convince yourself that the above is a valid trick:

Exercise 1

Argue that the last step above follows from the first three arguments.

Let us now formalize the argument for the number of iterations of the loop in Step 5 of the linear search algorithm. In this case we simply define $\mathcal{P}(i)=i$. Now consider the following four step argument:

  1. Note that at the end of the first iteration of the loop, we have $\mathcal{P}(1)=2$. (Here I am using the convention that in a for loop the value of the index gets incremented after the body of the loop is executed.)
  2. Since the index $i$ is incremented at the end of the $i$'th iteration, we have $\mathcal{P}(i)=i+1$. In particular, this implies that $\mathcal{P}(i+1)>\mathcal{P}(i)$.
  3. Since the loop is not executed if $i>n$, this implies that $\mathcal{P}(i)\le n+1$.
  4. Conclude that the number of iterations is upper bounded by $n+1 -2+1=n$, as desired.