Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions

Michal Ajdarów, Antonín Kučera

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 t…