An information-theoretic approach to time bounds for on-line computation (preliminary version)
Wolfgang J. Paul, Joel Seiferas, Janoš Šimon · 1980
Static, descriptional complexity (program size) [16, 9] can be used to obtain lower bounds on dynamic, computational complexity (such as running time). We describe and discuss this “information-theoretic approach” in the following section. Paul introduced it in [13], to obtain restricted lower bounds on the time complexity of sorting. We use the approach here to obtain lower time bounds for on-line simulation of one abstract storage unit by another. A major goal of our work is to promote the approach.