lower bounds how do know if have good algorithm to solve problemif my algorithm runs in th( log ntimeis that goodit would be if were sorting the records stored in an array but it would be terrible if were searching the array for the largest element the value of an algorithm must be determined in relation to the inherent complexity of the problem at hand in section we defined the upper bound for problem to be the upper bound of the best algorithm we know for that problemand the lower bound to be the tightest lower bound that we can prove over all algorithms for that problem while we usually can recognize the upper bound for given algorithmfinding the tightest lower bound for all possible algorithms is often difficultespecially if that lower bound is more than the "triviallower bound determined by measuring the amount of input that must be processed the benefits of being able to discover strong lower bound are significant in particularwhen we can make the upper and lower bounds for problem meetthis means that we truly understand our problem in theoretical sense it also saves us the effort of attempting to discover more efficient algorithms when no such algorithm can exist often the most effective way to determine the lower bound for problem is to find reduction to another problem whose lower bound is already known this is the subject of howeverthis approach does not help us when we cannot find suitable "similar problem our focus in this is discovering and proving lower bounds from first principles significant example of lower bounds argument is the proof from section that the problem of sorting is ( log nin the worst case section reviews the concept of lower bound for problem and presents the basic "algorithmfor finding good algorithm section discusses lower