variable xj. Intuitively, if P is continuous with respect to input xi and output xj, then an arbitrarily small change to the initial value of any xi, while keeping the remaining variables fixed, must only cause an arbitrarily small change to the final value of xj. Variables other than xj are allowed to change arbitrarily.

Formally, consider states s, s¢ of P and any  > 0. Let xi be a variable of type t, and let dt denote the metric over type t. We say that s and s¢ are -close with respect to xi, and write s ≈,i s¢, if dt(s (i), s¢(i) ) < . We call s¢ an -perturbation of s with respect to xi, and write s ≡,i s¢, if s and s¢ are -close with respect to xi, and further, for all j π i, we have s ( j) = s¢( j). Now we define: Definition 1 (Continuity). A program P is continuous at a state s with respect to an input variable xi and an output variable xj if for all  > 0, there exists a d > 0 such that for all s¢  S(P),

s ≡d,i s¢ ⇒ P (s) ≈, j P (s ′)

An issue with continuity is that it only certifies program behavior under arbitrarily small perturbations to the inputs. However, we may often want a definition of continuity that establishes a quantitative relationship between changes to a program’s inputs and outputs. Of the many properties in function analysis that accomplish this, Lipschitz continuity is perhaps the most well known. Let K > 0. A function f : R→R is K-Lipschitz continuous, or simply K-Lipschitz, if a ±-change to x can change f (x) by at most ±K. The constant K is known as the Lipschitz constant of f. It is easy to see that if f is K-Lipschitz for some K, then f is continuous at every input x.

We generalize this definition in two ways while adapting it to programs. First, as for continuity, we define Lipschitz continuity with respect to an input variable xi and an output variable xj. Second, we allow Lipschitz constants that depend on the size of the input. For example, suppose xi is an array of length N, and consider -changes to it that do not change its size. We consider P to be N-Lipschitz with respect to xi if on such a change, the output xj can change at most by N · . In general, a Lipschitz constant of P is a function K : N → R≥0 that takes the size of xi as an input.

Formally, to each value v, let us associate a size v > 0. If v is an integer or real, then v = 1; if v is an array of length N, then v = N. We have: Definition 2 (Lipschitz continuity). Let K : N → R≥0. The program P is K-Lipschitz with respect to an input xi and an output xj if for all s, s¢  S(P) and  > 0,

s ≡,i s¢ ∧ ( s (i) = s¢(i)) ⇒ P(s) ≈m, j P(s ′)

where m = K( s(i) ) · .

More generally, we could define Lipschitz continuity of
P within a subset S¢ of its state space. In such a definition,
s and s¢ in Definition 2 are constrained to be in S¢, and no
assertion is made about the effect of perturbations on states
outside S¢. Such a definition is useful because many realistic
programs are Lipschitz only within certain regions of their
input space, but for brevity, we do not consider it here.

Example 1 (Sorting). Let Sort be a sorting program that takes in an array A of reals and returns a sorted permutation of A. As discussed in Section 1, Sort is 1-Lipschitz in input A and output A, because any -change to the initial value of A (defined using our metric on arrays) can produce at most an -change to its final value. Note that this means that Sort is continuous in input A and output A at every program state.

What if A was an array of integers? Continuity still holds in this case, but for more trivial reasons. Since A is of a discrete type, the only arbitrarily small perturbation that can be made to A is no perturbation at all. Obviously, the program output does not change in this case. However, reasoning about continuity turns out to be important even under these terms. This is apparent when we try to prove that Sort is 1-Lipschitz when A is an array of integers. The easiest way to do this is to “cast” the input type of the program into an array of reals and prove that the program is 1-Lipschitz even after this modification, and this demands a proof of continuity.

Example 2 (Shortest paths). Let SP be a correct implementation of a shortest path algorithm. We view the graph G on which SP operates as an array of reals such that G[i] is the weight of the i-th edge. An -change to G thus amounts to a maximum change of ± to any edge weight of G, while keeping the node and edge structure intact.

The output of SP is the array d of shortest path distances in G—that is, d[i] is the length of the shortest path from the source node to the i-th node ui of G. We note that SP is N-Lipschitz in input G and output d (N is the number of edges in G). This is because if each edge weight in G changes by an amount , a shortest path weight can change at most by N · .

On the other hand, suppose SP had a second output: an array p whose i-th element is a sequence of nodes forming a minimal-weight path between src and ui. An -change to G may add or subtract elements from p—that is, perturb p by the amount ∞. Therefore, SP is not K-Lipschitz with respect to the output p for any K.

Example 3 (Minimum spanning trees). Consider any algorithm MST for computing a minimum-cost spanning tree in a graph G with real edge weights. Suppose MST has a variable c that holds, on termination, the cost of the minimum spanning tree. MST is N-Lipschitz (hence continuous everywhere) in the input G and the output c.

Example 4 (Knapsack). Consider the Knapsack problem from combinatorial optimization. We have a set of items { 1,…, N}, each item i associated with a real cost c[i] and a real value v[i]. We also have a nonnegative, real-valued budget. The goal is to identify a subset Used ⊆ { 1,…, N} such that the constraint SjOEUsed c[i] ≤ Budget is satisfied, and the value of totv = SjOEUsed v[i] is maximized.

Let our output variable be totv. As a perturbation can turn a previously feasible solution infeasible, a program Knap solving