focusing on the worst-case input an algorithm may run faster on some inputs than it does on others of the same size thuswe may wish to express the running time of an algorithm as the function of the input size obtained by taking the average over all possible inputs of the same size unfortunatelysuch an average-case analysis is typically quite challenging it requires us to define probability distribution on the set of inputswhich is often difficult task figure schematically shows howdepending on the input distributionthe running time of an algorithm can be anywhere between the worst-case time and the best-case time for examplewhat if inputs are really only of types "aor " "an average-case analysis usually requires that we calculate expected running times based on given input distributionwhich usually involves sophisticated probability theory thereforefor the remainder of this bookunless we specify otherwisewe will characterize running times in terms of the worst caseas function of the input sizenof the algorithm worst-case analysis is much easier than average-case analysisas it requires only the ability to identify the worst-case inputwhich is often simple alsothis approach typically leads to better algorithms making the standard of success for an algorithm to perform well in the worst case necessarily requires that it will do well on every input that isdesigning for the worst case leads to stronger algorithmic "muscles,much like track star who always practices by running up an incline running time (ms ms ms worst-case time average-case time ms best-case time ms ms input instance figure the difference between best-case and worst-case time each bar represents the running time of some algorithm on different possible input