On the Philosophy of Statistical Bounds: A Case Study on a Determinant Algorithm

Under the umbrella of statistical algorithmic complexity (which some authors call stochastic arithmetic) , it makes sense to talk about statistical bounds (asymptotic) and their empirical estimates over a finite range (a computer experiment cannot be run for infinite input size!), the so called empirical O, which were informally introduced in Chakraborty and Sourabh where it was shown that they make average complexity more meaningful. The present study shows that these concepts can be used effectively in worst cases as well as in best cases besides average cases with a case study on an efficient determinant algorithm.