Potential Function Analysis (6b)

Michael L. Littman

September 17th, 1998

1 METHODS OF ANALYSIS

1.1 Language-Oriented Analysis

We’ve looked at several different kinds of analyses. One way to think about it is that different ways of writing loops correspond to different analysis methods. Are loops all that really matters in analysis?

• for loops: multiply run time of each iteration times the number of iterations;

• recursion: recurrence relations;

• while: today.

Let’s look at each of these using our all-purpose guinea-pig algorithm.

1.2 Return to Russia

Here’s Russian with a for loop. Why does this work?

int Russian(int a, int b)
//  implements Russian Peasant Algorithm
{
   int x = a, y = b, z = 0, i;
   for (i = 0; i < log(a); i++)
   {
      if ( 1 == x % 2)
         z += y;
      y <<= 1;
      x >>= 1;
   }
   return z;
}

Upper bound is easy.

1.3 Recursive

int RussianRec(int a, int b)
//  implements Russian Peasant Algorithm recursively
{
  if (a == 0) return 0;
  else if ( 1 == a % 2)
    return(b+ RussianRec(a >> 1, b) << 1);
  else
    return(RussianRec(a >> 1, b) << 1);
}

Gives T (0) = 0, T (a) = 1 + T (a/2). By now, this is familiar.

1.4 The While Version

int Russian(int a, int b)
//  implements Russian Peasant Algorithm
{
   int x = a, y = b, z = 0;
   while (x > 0)
   {
      if ( 1 == x % 2)
         z += y;
      y <<= 1;
      x >>= 1;
   }
   return z;
}

This is the first one we saw. How can we analyze it?

1.5 Dealing with while loops

Now, we’ve seen several ways of analyzing algorithms with while loops.

• Convert it into a for loop or a recursive algorithm.

• Treat it as a for loop by finding an upper bound.

• Use a potential function analysis.

2 POTENTIAL FUNCTION ANALYSIS

2.1 Motivation

For some algorithms, conversion to a for loop or recursion is awkward because of side effects, and upper bounds on the number of iterations are too loose. In such a case, treating each iteration independently doesn’t work. We need to analyze the whole loop at once. But, in general, this kind of analysis is too hard. We need something that captures the iteration-by-iteration behavior while also dealing sensibly with side effects.

2.2 In-Place Permutation Sorting

Puzzle: Array A contains elements whose keys are a permutation of the numbers zero through n − 1. How fast can we sort A using swaps? Well, O(n^{2}) and O(n log n) ought to be easy, yes? Can we do better? 5 3 0 4 6 2 7 1 9 8

2.3 An Algorithm

void indexsort( vector<int> & data)
{
   int i, n = data.size();
   for (i = 0; i < n; i++)
   {
      while(data[i] != i)
         swap(data, i, data[i]);
   }
}

Analyze via upper bound.

2.4 Empirical Observation

Running time of O(n^{2}) suggests that we’d be better off with quicksort. Not so.

A failure of analysis!

2.5 Intuitive Analysis

Here’s how to see that this is linear time. All the work is in doing swaps, and in incrementing i if no swap is needed. How many times can we increment i? How many times can we do swaps? So, all the work is O(n). Potential function analysis is just a more formal way of making this argument.

2.6 Potential Function Basics

The basic idea is that we define a function Φ(D) over the space of program states that measures the amount of “work” left to be squeezed out (potential energy). Properties:

• Φ(D) ≥ 0

We’ll think of the program as performing a series of k operations starting on the initial state D_{0}, D_{1}, D_{2}, …, D_{k}.

2.7 Amortized Cost

Let c_{i} be the true cost of the ith operation. Define ĉ_{i} to be the amortized cost. We insist that

c_{i} ≤ ĉ_{i} + Φ(D_{i−1}) − Φ(D_{i}).

The idea here is that analyzing the true costs will be too difficult, but the amortized costs will be easier to deal with. The “slack” between the two costs is picked up by the potential function.

2.8 Fundamental Potential Function Inequality

We’ve got a sequence of k operations. D_{i} is the state of the computation after i operations. D_{0} is the initial program state.

∑_{i=1}^{k} c_{i} ≤ ∑_{i=1}^{k}(ĉ_{i} + Φ(D_{i−1}) − Φ(D_{i}))
= ĉ_{1} + Φ(D_{0}) − Φ(D_{1}) + ĉ_{2} + Φ(D_{1}) − Φ(D_{2}) + …
= ∑_{i=1}^{k} ĉ_{i} + Φ(D_{0}) − Φ(D_{k})

2.9 Using the Inequality

For the type of analysis we’re talking about today, we insist that ĉ_{i} = 0, and Φ(D_{k}) = 0. Using the fundamental inequality, we get:

∑_{i=1}^{k} c_{i} ≤ ∑_{i=1}^{k} ĉ_{i} + Φ(D_{0}) − Φ(D_{k})
= Φ(D_{0}).

Thus, the maximum value of the potential function gives a worst-case bound on total running time. The potential function measures the work it will take to solve the problem.

2.10 Analysis of Permutation Problem

void indexsort( vector<int> & data)
{
   int i, n = data.size();
   for (i = 0; i < n; i++)
   {
      while(data[i]-1 != i)
         swap(data, i, data[i]-1);
   }
}

Here are the steps for potential function analysis:

• Define the “operations”:

For this problem, the operations are the execution of the swap call or the increment of the index i if no swap is needed.

• Define the potential function:

Φ(A, i) = (n − i) + ∑_{j=0}^{n−1} χ(A[j] ≠ j).

Here, χ(e) is the indicator function: one if e is true, and zero otherwise. So, Φ(A, i) measures the distance of i from n plus the number of items still unsorted. Note that the potential function need not be computable quickly. It’s mainly a mathematical definition.

• Define the amortized costs: ĉ_{t} = 0.

• Show that c_{t} ≤ ĉ_{t} + Φ(A_{t−1}, i_{t−1}) − Φ(A_{t}, i_{t}): Here, A_{t} and i_{t} means the array and index after the tth operation. In this case, there are two operations: Swapping and incrementing i. We swap if A[i] is out of place. Then, c_{t} = 1, and

ĉ_{t} + Φ(A_{t−1}, i_{t−1}) − Φ(A_{t}, i_{t})
= 0 + (n − i_{t−1}) + ∑_{j=0}^{n−1} χ(A_{t−1}[j] ≠ j)

−(n − i_{t}) − ∑_{j=0}^{n−1} χ(A_{t}[j] ≠ j)

≥ (n − i_{t−1}) + ∑_{j=0}^{n−1} χ(A_{t−1}[j] ≠ j)

−(n − i_{t−1}) − (∑_{j=0}^{n−1} χ(A_{t−1}[j] ≠ j) − 1)

≥ 1 = c_{t}.

If we increment i, then c_{t} = 1, and

ĉ_{t} + Φ(A_{t−1}, i_{t−1}) − Φ(A_{t}, i_{t})
= 0 + (n − i_{t−1}) + ∑_{j=0}^{n−1} χ(A_{t−1}[j] ≠ j)

−(n − i_{t}) − ∑_{j=0}^{n−1} χ(A_{t}[j] ≠ j)

= (n − i_{t−1}) + ∑_{j=0}^{n−1} χ(A_{t−1}[j] ≠ j)

−(n − (i_{t−1} + 1)) − ∑_{j=0}^{n−1} χ(A_{t−1}[j] ≠ j)

= 1 = c_{t}.

• Now, the total work in the sequence of operations is bounded by the maximum initial value of the potential function.

Φ(A_{0}, i_{0}) = (n − i_{0}) + ∑_{j=0}^{n−1} χ(A_{0}[j] ≠ j)

≤ (n − 0) + ∑_{j=0}^{n−1} 1
= 2n.

2.11 Punch Line

By this analysis, index sort runs in O(n)... no wonder it runs so fast! The basic idea is that we find something that changes on each iteration (either i is incremented, or at least one new item is put in its place). This gives us a way to bound the total work before the algorithm terminates.

3 EXAMPLES

3.1 While in Russia...

We can analyze the “while” version of the Russian Peasant’s algorithm the same way.

int Russian(int a, int b)
//  implements Russian Peasant Algorithm
{
   int x = a, y = b, z = 0;
   while (x > 0)
   {
      if ( 1 == x % 2)
         z += y;
      y <<= 1;
      x >>= 1;
   }

return z;
}

• Define the “operations”:

Only one: the body of the loop.

• Define the potential function: Φ(x) = log(x).

• Define the amortized costs: ĉ_{t} = 0.

• Show that c_{t} ≤ ĉ_{t} + Φ(x_{t−1}) − Φ(x_{t}):

Within the loop, we do constant work, so c_{t} = 1.

ĉ_{t} + Φ(x_{t−1}) − Φ(x_{t})
= 0 + log(x_{t−1}) − log(x_{t})
= log(x_{t−1}) − log(⌊x_{t−1}/2⌋)
≥ log(x_{t−1}) − log(x_{t−1}/2) + 1
= log(x_{t−1}) − log(x_{t−1}) + 1 + 1
= 2 ≥ c_{t}.

• Now, the total work in the sequence of operations is bounded by the maximum initial value of the potential function: Φ(x_{0}) = log(x_{0}) = log(a).

3.2 Quicksort Pivot

int partition( vector<int> & A, int start, int end, int pivot_position )
{
int x = A[pivot_position];
int i = start - 1;
int j = end + 1;
while( true )
{
do j--;
while( A[j] > x );
do i++;
while( A[i] < x );
if( i < j )
  swap( A, i, j );
else
  return j;

}
}

• Define the “operations”:

(1) Decrement j, (2) Increment i, (3) Swap.

• Define the potential function:

Φ(A, i, j) = 2j − 2i + χ(A[j] ≤ x) + χ(A[i] ≥ x).

• Define the amortized costs: ĉ_{t} = 0.

• Show that c_{t} ≤ ĉ_{t} + Φ(x_{t−1}) − Φ(x_{t}):

In all cases, c_{t} = 1.

(1) Decrement j:

ĉ_{t} + Φ(A_{t−1}, i_{t−1}, j_{t−1}) − Φ(A_{t}, i_{t}, j_{t})
≥ 0 + 2j_{t−1} − 2(j_{t−1} − 1) − 1
= 1 = c_{t}.

(2) Increment i:

ĉ_{t} + Φ(A_{t−1}, i_{t−1}, j_{t−1}) − Φ(A_{t}, i_{t}, j_{t})
≥ 0 − 2i_{t−1} + 2(i_{t−1} + 1) − 1
= 1 = c_{t}.

(3) Swap:

ĉ_{t} + Φ(A_{t−1}, i_{t−1}, j_{t−1}) − Φ(A_{t}, i_{t}, j_{t})

= χ(A_{t−1}[j_{t−1}] ≤ x) + χ(A_{t−1}[i_{t−1}] ≥ x) − χ(A_{t}[j_{t}] ≤ x) − χ(A_{t}[i_{t}] ≥ x)
= 1 + 1 − 1 − 0 = 1 = c_{t}.

Note: This is assuming at most one value equal to the pivot.

• Now, the total work in the sequence of operations is bounded by the maximum initial value of the potential function: Φ(A_{0}, i_{0}, j_{0}) ≤ 2n + 2.

3.3 Web Walk

page_list webwalk( page_list start_page )
{
page_list foundpages = start_page;
page_list explored_pages;
while ( foundpages != empty_list )
{
any_page = pick any of foundpages;
newpage = explore(any_page);
if (newpage == NULL)
{
  foundpages -= any_page;
  explored_pages += any_page;
} else
{
  foundpages += newpage;
}
}
return explored_pages;
}

• Define the “operations”:

(1) Done with any page, (2) Found a new page.

• Define the potential function:

Φ(f, e) = n − (f + 2e).

Let n be the size of the final list.

• Define the amortized costs: ĉ_{t} = 0.

• Show that c_{t} ≤ ĉ_{t} + Φ(x_{t−1}) − Φ(x_{t}):

In all cases, c_{t} = 1.

(1) Done with any page:

ĉ_{t} + Φ(f_{t−1}, e_{t−1}) − Φ(f_{t}, e_{t})

= 0 + n − (f_{t−1} + 2e_{t−1}) − (n − (f_{t} + 2e_{t}))
= −f_{t−1} − 2e_{t−1} + f_{t} + 2e_{t}
= −f_{t−1} − 2e_{t−1} + (f_{t−1} − 1) + 2(e_{t−1} + 1)
= 1 = c_{t}.

(2) Found a new page:

ĉ_{t} + Φ(f_{t−1}, e_{t−1}) − Φ(f_{t}, e_{t})

= 0 + n − (f_{t−1} + 2e_{t−1}) − (n − (f_{t} + 2e_{t}))
= −f_{t−1} − 2e_{t−1} + f_{t} + 2e_{t}
= −f_{t−1} − 2e_{t−1} + (f_{t−1} + 1) + 2(e_{t−1})
= 1 = c_{t}.

• Now, the total work in the sequence of operations is bounded by the maximum initial value of the potential function: Φ(f_{0}, e_{0}) = n − (f_{0} + 2e_{0}) = n − 1.