A note on the best-case complexity (Q1120281)

Four aspects of complexity are discussed: almost everywhere vs. infinitely often and best-case vs. worst-case. Three main results are proved. First, the most of the basic propositions of almost everywhere worst case complexity can be extended to the other cases: almost everywhere best- case, infinitely often best-case and infinitely often worst-case. Second, there exist languages recognized almost everywhere in worst time bound \(g(n)\) that cannot be recognized in almost everywhere best-case time complexity \(f(n)\), where \(g(n)\) and \(f(n)\) are slightly separated. Third, there exist languages not even computable infinitely often in best-case space \(f(n)\) that are easy to compute almost everywhere in worst- case space \(g(n)\), with \(f\) and \(g\) very close. The last section includes some open questions and discusses the issue of nondeterminism.