chap algorithm analysis values if we implement sequential search as program and run it many times on many different arrays of size nor search for many different values of within the same arraywe expect the algorithm on average to go halfway through the array before finding the value we seek on averagethe algorithm examines about / values we call this the average case for this algorithm when analyzing an algorithmshould we study the bestworstor average casenormally we are not interested in the best casebecause this might happen only rarely and generally is too optimistic for fair characterization of the algorithm' running time in other wordsanalysis based on the best case is not likely to be representative of the behavior of the algorithm howeverthere are rare instances where best-case analysis is useful -in particularwhen the best case has high probability of occurring in you will see some examples where taking advantage of the best-case running time for one sorting algorithm makes second more efficient how about the worst casethe advantage to analyzing the worst case is that you know for certain that the algorithm must perform at least that well this is especially important for real-time applicationssuch as for the computers that monitor an air traffic control system hereit would not be acceptable to use an algorithm that can handle airplanes quickly enough most of the timebut which fails to perform quickly enough when all airplanes are coming from the same direction for other applications -particularly when we wish to aggregate the cost of running the program many times on many different inputs -worst-case analysis might not be representative measure of the algorithm' performance often we prefer to know the average-case running time this means that we would like to know the typical behavior of the algorithm on inputs of size unfortunatelyaverage-case analysis is not always possible average-case analysis first requires that we understand how the actual inputs to the program (and their costsare distributed with respect to the set of all possible inputs to the program for exampleit was stated previously that the sequential search algorithm on average examines half of the array values this is only true if the element with value is equally likely to appear in any position in the array if this assumption is not correctthen the algorithm does not necessarily examine half of the array values in the average case see section for further discussion regarding the effects of data distribution on the sequential search algorithm the characteristics of data distribution have significant effect on many search algorithmssuch as those based on hashing (section and search trees ( see section incorrect assumptions about data distribution can have dis