chap algorithm analysis bubble sort and insertion sort algorithms typically given as examples in first year programming course have worst case running times in ( thusthe problem of sorting can be said to have an upper bound in ( how do we close the gap between ohm(nand ( )can there be better sorting algorithmif you can think of no algorithm whose worst-case growth rate is better than ( )and if you have discovered no analysis technique to show that the least cost for the problem of sorting in the worst case is greater than ohm( )then you cannot know for sure whether or not there is better algorithm presents sorting algorithms whose running time is in ( log nfor the worst case this greatly narrows the gap with this new knowledgewe now have lower bound in ohm(nand an upper bound in ( log nshould we search for faster algorithmmany have triedwithout success fortunately (or perhaps unfortunately?) also includes proof that any sorting algorithm must have running time in ohm( log nin the worst case this proof is one of the most important results in the field of algorithm analysisand it means that no sorting algorithm can possibly run faster than cn log for the worst-case input of size thuswe can conclude that the problem of sorting is th( log nin the worst casebecause the upper and lower bounds have met knowing the lower bound for problem does not give you good algorithm but it does help you to know when to stop looking if the lower bound for the problem matches the upper bound for the algorithm (within constant factor)then we know that we can find an algorithm that is better only by constant factor common misunderstandings asymptotic analysis is one of the most intellectually difficult topics that undergraduate computer science majors are confronted with most people find growth rates and asymptotic analysis confusing and so develop misconceptions about either the concepts or the terminology it helps to know what the standard points of confusion arein hopes of avoiding them one problem with differentiating the concepts of upper and lower bounds is thatfor most algorithms that you will encounterit is easy to recognize the true growth rate for that algorithm given complete knowledge about cost functionthe upper and lower bound for that cost function are always the same thusthe distinction between an upper and lower bound is only worthwhile when you have incomplete knowledge about the thing being measured if this distinction is still not while it is fortunate to know the truthit is unfortunate that sorting is th( log nrather than th( )