Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.