clearreread section we use th-notation to indicate that there is no meaningful difference between what we know about the growth rates of the upper and lower bound (which is usually the case for simple algorithmsit is common mistake to confuse the concepts of upper bound or lower bound on the one handand worst case or best case on the other the bestworstor average cases each give us concrete instance that we can apply to an algorithm description to get cost measure the upper and lower bounds describe our understanding of the growth rate for that cost measure so to define the growth rate for an algorithm or problemwe need to determine what we are measuring (the bestworstor average caseand also our description for what we know about the growth rate of that cost measure (big-ohohmor ththe upper bound for an algorithm is not the same as the worst case for that algorithm for given input of size what is being bounded is not the actual cost (which you can determine for given value of )but rather the growth rate for the cost there cannot be growth rate for single pointsuch as particular value of the growth rate applies to the change in cost as change in input size occurs likewisethe lower bound is not the same as the best case for given size another common misconception is thinking that the best case for an algorithm occurs when the input size is as small as possibleor that the worst case occurs when the input size is as large as possible what is correct is that bestand worsecase instances exist for each possible size of input that isfor all inputs of given sizesay ione (or moreof the inputs of size is the best and one (or moreof the inputs of size is the worst often (but not always!)we can characterize the best input case for an arbitrary sizeand we can characterize the worst input case for an arbitrary size ideallywe can determine the growth rate for the bestworstand average cases as the input size grows example what is the growth rate of the best case for sequential searchfor any array of size nthe best case occurs when the value we are looking for appears in the first position of the array this is true regardless of the size of the array thusthe best case (for arbitrary size noccurs when the desired value is in the first of positionsand its cost is it is not correct to say that the best case occurs when example imagine drawing graph to show the cost of finding the maximum value among valuesas grows that isthe axis would be nand the value would be the cost of coursethis is diagonal line