# Complexity of the stack algorithm

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

$R_0 = 1-\log_2\left(\sqrt{\mathbf{Pr}\left[ \textnormal{bit error}\right]}+\sqrt{1-\mathbf{Pr}\left[ \textnormal{bit error}\right]}\right)^2$

As long as $R \leq R_0$, we have that

$\mathbf{E}\left[ C_i \right] = \textnormal{\# computations for symbol } i < \infty$

The computation time has the distribution

$\mathbf{Pr}\left[ C_i \geq \psi\right] \approx A\psi^{-\rho}, \quad 0 < \rho < \infty, \quad 0 \leq i \leq k$

where $\rho$ is the pareto exponent. $\rho$ satisfies the equation

$R = \frac{\rho-\log_2\left( \left( \mathbf{Pr}\left[ \textnormal{bit error}\right]\right)^{1/(1+\rho)}+ \left( 1-\mathbf{Pr}\left[ \textnormal{bit error}\right]\right)^{1/(1+\rho)}\right)^{1+\rho}}{\rho}$

Since

$\mathbf{Pr}\left[ C_i \geq \psi\right] = F_{C_i}(\psi) = \int_\psi^\infty f_{C_i}(x)$

we can find

$f_{C_i}(x) = \frac{d}{dx}F_{C_i}(x) = -\rho Ax^{-\rho-1}$

So the expected value

$\mathbf{E}\left[ C_i \right] = \int_0^\infty xf_{C_i}(x) = -\int_0^\infty \rho Ax^{-\rho} = A\rho\left[ \frac{x^{1-\rho}}{1-\rho} \right]_0^\infty$

Hence, we get

$\mathbf{E}\left[ C_i \right] = \lim_{x\rightarrow \infty}\frac{A\rho}{1-\rho}(x^{1-\rho}-1)$

So given that $R \leq R_0$, we have that $\rho \geq 1 \implies \mathbf{E}\left[ C_i \right] < \infty$.