Indeed the bounds on convergence times t_0 and tau depend on quantities that are expensive to compute. For example, if we consider the norm of A, this quantity can itself be bound by the values the elements A can take itself, which is a requirement on the type of hardware we would be using (as the elements of A are mapped to component values in the hardware that is considered in the appendix). There are other heuristic tricks one could use.

To give a comparison with conjugate gradients, there the condition number is in the convergence bound, however computing it requires the maximum and minimum eigenvalues, hence people never compute it, and rely on heuristics for convergence.