chap patterns of algorithms randomized algorithms for finding large values in section we determined that the lower bound cost of finding the maximum value in an unsorted list is ohm(nthis is the least time needed to be certain that we have found the maximum value but what if we are willing to relax our requirement for certaintythe first question is what do we mean by thisthere are many aspects to "certaintyand we might relax the requirement in various ways there are several possible guarantees that we might require from an algorithm that produces as the maximum valuewhen the true maximum is is ' rank is "close toy ' rank(rank( <rank( "small is "usuallyy ( ( >"large ' rank is "usually"closeto ' rank each of these guarantees leads to type of algorithms as follows exact or deterministic algorithm approximation algorithm probabilistic algorithm heuristic there are also ways that we might choose to sacrifice reliability for speed these types of algorithms also have names las vegas algorithmswe always find the maximum valueand "usuallywe find it fast such algorithms have guaranteed resultbut not guaranteed fast running time monte carlo algorithmswe find the maximum value fastor we don' get an answer at all (but fastsuch algorithms have good running timetheir result is not guaranteed here is an example of an algorithm for finding large value that gives up its guarantee of getting the best value in exchange for an improved running time this is an example of probabilistic algorithmsince it includes steps that are affected by random events choose elements at randomand pick the best one of those as the answer for large nif log nthe answer is pretty good the cost is compares (since we must find the maximum of valuesbut we don' know for sure what we will get howeverwe can estimate that the rank will be mn about + nextconsider slightly different problem where the goal is to pick number in the upper half of values we would pick the maximum from among the first + values for cost of / comparisons can we do better than thisnot if we