binary search requires that the array values be ordered from lowest to highest depending on the context in which binary search is to be usedthis requirement for sorted array could be detrimental to the running time of complete programbecause maintaining the values in sorted order requires to greater cost when inserting new elements into the array this is an example of tradeoff between the advantage of binary search during search and the disadvantage related to maintaining sorted array only in the context of the complete problem to be solved can we know whether the advantage outweighs the disadvantage analyzing problems you most often use the techniques of "algorithmanalysis to analyze an algorithmor the instantiation of an algorithm as program you can also use these same techniques to analyze the cost of problem it should make sense to you to say that the upper bound for problem cannot be worse than the upper bound for the best algorithm that we know for that problem but what does it mean to give lower bound for problemconsider graph of cost over all inputs of given size for some algorithm for given problem define to be the collection of all algorithms that solve the problem (theoreticallythere an infinite number of such algorithmsnowconsider the collection of all the graphs for all of the (infinitely manyalgorithms in the worst case lower bound is the least of all the highest points on all the graphs it is much easier to show that an algorithm (or programis in ohm( ( )than it is to show that problem is in ohm( ( )for problem to be in ohm( ( )means that every algorithm that solves the problem is in ohm( ( ))even algorithms that we have not thought ofso far all of our examples of algorithm analysis give "obviousresultswith big-oh always matching ohm to understand how big-ohohmand th notations are properly used to describe our understanding of problem or an algorithmit is best to consider an example where you do not already know lot about the problem let us look ahead to analyzing the problem of sorting to see how this process works what is the least possible cost for any sorting algorithm in the worst casethe algorithm must at least look at every element in the inputjust to determine that the input is truly sorted it is also possible that each of the values must be moved to another location in the sorted output thusany sorting algorithm must take at least cn time for many problemsthis observation that each of the inputs must be looked at leads to an easy ohm(nlower bound in your previous study of computer scienceyou have probably seen an example of sorting algorithm whose running time is in ( in the worst case the simple