Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know that in general it is hard to analyze the average-case (time) complexity of an algorithm. It is challenging to make meaningful assumptions about the distribution of the inputs and/or sometimes it's next to impossible to say what a typical input object is (what's a typical polynomial/graph/automaton/whatever).

Is this the reason for not seeing formal average-case analysis of even trivial or easy algorithms, say Horner's algorithm? Or is this something that could or has been done, but is of no (practical) interest since the algorithm will solve the problem "quickly" anyway? I can imagine that atleast for computationally hard problems the average-case is very useful and important.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.