This paper presents a number of bounds on the parallel processor evaluation of arithmetic expressions. Several previous papers show that if the evaluation of an expression using a serial computer requires t operations, by using a number of processors in parallel, the expression may be evaluated in time proportional to $\log _2 t$. Since $\log _2 t$ is an obvious lower bound, it is of interest to attempt to approach this bound. The present paper shows that if more information than the number of operations (or operands) is known, sharper bounds may be given in certain cases. Thus if the number of parenthesis pairs is small or if the depth of parenthesis nesting is small, we may approach the lower bound. A new bound is also given for expressions which have few division operations. Similarly, if the expression’s form is restricted, sharper bounds may be found. Thus generalizations of polynomials and generalizations of continued fractions are shown to have improved bounds. We also give a new bound for expressions without division operations which have a limited number of parenthesis pairs. Finally, we give an upper bound on the time to evaluate expressions in which multiplication is not commutative.

If an unlimited number of processors is available, then for any given number of steps s, s≥1, polynomials of degree as large as C2n-δcan be evaluated, where C= √2 and δ ≈ √2s. This implies polynomials of degree can be evaluated in log2n+√2log2n +0(1) steps. Various techniques for the evaluation of polynomials in a "reasonable number" of "steps" are compared with the known lower bounds.