1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ What would that look like? The average over the worst 10% of cases, for example? $\endgroup$ Commented Jan 18, 2017 at 11:15
  • $\begingroup$ @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. $\endgroup$
    – user7060
    Commented Jan 18, 2017 at 16:21

1 Answer 1

2
$\begingroup$

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.

The simplex algorithm has been shown to be polynomial time in this sense, although its worst case complexity is exponential.

$\endgroup$
7
  • $\begingroup$ Thank you ! Again ! :-) . Are you aware of a notion in which we compute the average complexity of a probabilistic algorithm by considering the worst choices of random coins? $\endgroup$
    – user7060
    Commented Jan 18, 2017 at 16:24
  • $\begingroup$ I'm not sure why you would do that. It is better to just fix them arbitrarily and analyze the corresponding deterministic algorithm. $\endgroup$ Commented Jan 18, 2017 at 16:32
  • $\begingroup$ Because I think these random choices can completely determine the efficiency of the algorithm. It is motivated by the fact that a worst case input is often "isolated", not representative of the average worst case. $\endgroup$
    – user7060
    Commented Jan 18, 2017 at 16:59
  • $\begingroup$ After I have read again your answer, I understand that worst case should better analysed depending on the distribution of the input. But, concerning non-deterministic algorithms, are there types of analysis that are focusing on the complexity of the algorithm depending on the distribution of the coin tosses, rather than on the input distribution ? $\endgroup$
    – user7060
    Commented Jan 18, 2017 at 18:24
  • $\begingroup$ Pseudorandomness focuses on what assumptions on the coin tosses are needed to guarantee a random-like behavior. $\endgroup$ Commented Jan 18, 2017 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.