On the average number of registers required for evaluating arithmetic expressions
Philippe Flajolet, Jean-Claude Raoult, Jean E. Vuillemin · 1977
Let An be the average number of registers required for evaluating arithmetic expressions of size n, or, equivalently, the minimal stack needed for exploring binary trees with n nodes. We give explicit expressions for An and related quantities and show that: An = log4(n) + C + E(log4n) + o(1) where C = 1/2 - γ + 2/2 log2 + log2Π 0.292 and E is continuous, periodic with period 1, with average value 0 and amplitude less than .05.