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
.