  The standard approach to analyzing the asymptotic complexity of probabilistic
programs is based on studying the asymptotic growth of certain expected values
(such as the expected termination time) for increasing input size. We argue
that this approach is not sufficiently robust, especially in situations when
the expectations are infinite. We propose new estimates for the asymptotic
analysis of probabilistic programs with non-deterministic choice that overcome
this deficiency. Furthermore, we show how to efficiently compute/analyze these
estimates for selected classes of programs represented as Markov decision
processes over vector addition systems with states.
