how well particular sorting algorithms compare against that theoretical lower bound in generalquestions of this kind are rather hardbecause of the need to consider all possible algorithms in factfor some problemsoptimal lower bounds are not yet known one important example is the so-called travelling salesman problem (tsp)for which all algorithmswhich are known to give the correct shortest route solutionare extremely inefficient in the worst case (many to the extent of being useless in practicein these casesone generally has to relax the problem to find solutions which are probably approximately correct for the tspit is still an open problem whether there exists feasible algorithm that is guaranteed to give the exact shortest route for sorting algorithms based on comparisonshoweverit turns out that tight lower bound does exist clearlyeven if the given collection of items is already sortedwe must still check all the items one at time to see whether they are in the correct order thusthe lower bound must be at least nthe number of items to be sortedsince we need at least steps to examine every element if we already knew sorting algorithm that works in stepsthen we could stop looking for better algorithmn would be both lower bound and an upper bound to the minimum number of stepsand hence an exact bound howeveras we shall shortly seeno algorithm can actually take fewer than (nlog ncomparisons in the worst case ifin additionwe can design an algorithm that works in (nlog nstepsthen we will have obtained an exact bound we shall start by demonstrating that every algorithm needs at least (nlog ncomparisons to begin withlet us assume that we only have three itemsijand if we have found that < and <kthen we know that the sorted order isijk so it took us two comparisons to find this out in some caseshoweverit is clear that we will need as many as three comparisons for exampleif the first two comparisons tell us that and <kthen we know that is the smallest of the three itemsbut we cannot say from this information how and relate third comparison is needed so what is the average and worst number of comparisons that are neededthis can best be determined from the so-called decision treewhere we keep track of the information gathered so far and count the number of comparisons needed the decision tree for the three item example we were discussing isi < yes no < < yes no yes < < < yes < < no < < < no yes < < < < no < < so what can we deduce from this about the general casethe decision tree will obviously always be binary tree it is also clear that its height will tell us how many comparisons will be needed in the worst caseand that the average length of path from the root to leaf will give us the average number of comparisons required the leaves of the decision tree are