Abstract
A study of the general properties of incremental algorithms is presented. First, it is shown that within certain limitations it is not possible for an incremental algorithm to be of complexity less than 11n of that of the best non-incremental algorithm for any given function. Next we describe a model theorem for any given function. Next we describe a model for incremental algorithms based on a generalization of finite state machines. It is demonstrated that all finite state machines have either constant or linear complexity, and this is extended to a subclass of incremental algorithms. Then the requirements for machines with good incremental algorithms or discussed, and two classes are presented, one which can be updated in constant time, and one in V_n time, when averaged over a sequence of changes.