The complexity of the stack algorithm is non-deterministic. As long as the rate of the code is less than the *computational cutoff rate*, the expected complexity is bounded.

The computational cutoff rate is given by

As long as , we have that

The computation time has the distribution

where is the pareto exponent. satisfies the equation

Since

we can find

So the expected value

Hence, we get

So given that , we have that .

Advertisements