what is average case analysis?

Question

Hello again guys,

question 1: why is average case analysis more difficult to carry out than the worst case analysis. got to think of alteast 4 points, thought of 1, am i right?

answer: Algorithm exist for which no such analysis has been possible

question 2: what is elementary operation in terms of time measure? and why is time-demand of an algorithm measured in terms of elementary operations instead of CPU TIME?

answer: Time consuming and less simplicity.(no sure about these), could anyone suggest? and even thought of cost

Answer 1

There are several points about average case analysis in the Best, worst and average case Wikipedia article. See the section on Worst-case versus average-case performance.

For your second question, an elementary operation is the basic computation performed by an algorithm. For example, the elementary operation in Bubble sort is the swap operation. We use elementary operations because they can be assumed to be largely independent of the hardware, platform, and programming language used to implement the algorithm. You wouldn't measure time-demand in CPU time because that's going to be dependent on all of these things. An algorithm can be implemented in many different languages, and will be executed on many different machines. You analysis should not be dependent on one particular machine or implementation.