# Average case complexity of search data structures

Algorithms are generally studied in terms of average case complexity and worst case complexity? Is there also a kind of analysis called "average worst case" complexity?

• What would that look like? The average over the worst 10% of cases, for example? Commented Jan 18, 2017 at 11:15
• @PeterLeupold I was thinking about algorithms that depend on random coins. The choice of these random coins could sometimes lead to poor efficiency. We then compute the average complexity considering the worst choices. Commented Jan 18, 2017 at 16:21

One such notion is that of smoothed analysis, in which we compute the worst-case expected complexity of an algorithm on a randomly perturbed input. In more detail, let $N(x)$ be a randomly perturbed version of $x$, and let $T$ be the time complexity of the algorithm. Then we are interested in $$\sup_x \mathbb E[T(N(x))].$$ The "worst case" aspect is with respect to the unperturbed input, and the "average case" aspect is with respect to the perturbation.