Review

This is a linkpost for http://arxiv.org/abs/1601.03411

Analysis of Algorithms and Partial Algorithms

0Vanessa Kosoy

New Comment

1 comment, sorted by Click to highlight new comments since: Today at 7:58 AM

The mean running time is usually *not* used in average-case complexity theory because it is not well-behaved under changing the model of computation. Your example is in the class . For a good overview of average-case complexity theory see Bogdanov and Trevisan.