The theme of this collection of papers is the derivation of rigorous bound on the cost of certain computations. Cost may be measured in several different ways. For example, in [37, 39, 45, 50] we identify cost with the number of arithmetic operations performed on integers or real numbers, in [32, 34] we consider the number of Boolean operations, and in [12, 14, 16] we count function and derivative evaluations. In [3, 15, 18, 22] it is more appropriate to consider the time required to evaluate an expression on a parallel machine, and in [55, 60] we introduce an area-time product which is motivated by practical cost measures for VLSI circuits.
Most of the papers are concerned with upper bounds, which are established by exhibiting an algorithm and analysing its performance. In [16, 55] nontrivial lower bounds are established. Proofs of lower bounds are generally more difficult than those for upper bounds, since it is necessary to consider all possible algorithms for the problem at hand, rather than just one carefully selected algorithm. The aim when establishing upper and lower bounds is, of course, to bring them as close together as possible, but this is difficult unless the "trivial" lower bound is almost attainable, as in .
The collection is divided into the following sections.
The papers included are [3, 12, 13, 14, 15, 16, 18, 22, 27, 28, 32, 34, 37, 39, 45, 50, 55, 60].
introduction: 9, 10, 11, 12, 13, 14;
bibliography: 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26.
other sections: see the papers mentioned in the abstract above.
All the above gif files are available in a single pdf file (1346K).
Go to next publication
Return to Richard Brent's index page