chap algorithm analysis sequential search is practical for large nin way that is not true for some other algorithms in ( we always seek to define the running time of an algorithm with the tightest (lowestpossible upper bound thuswe prefer to say that sequential search is in (nthis also explains why the phrase "is in ( ( ))or the notation ( ( ))is used instead of "is ( ( ))or " ( ( )there is no strict equality to the use of big-oh notation (nis in ( )but ( is not in (nlower bounds big-oh notation describes an upper bound in other wordsbig-oh notation states claim about the greatest amount of some resource (usually timethat is required by an algorithm for some class of inputs of size (typically the worst such inputthe average of all possible inputsor the best such inputsimilar notation is used to describe the least amount of resource that an algorithm needs for some class of input like big-oh notationthis is measure of the algorithm' growth rate like big-oh notationit works for any resourcebut we most often measure the least amount of time required and againlike big-oh notationwe are measuring the resource required for some particular class of inputsthe worst-average-or best-case input of size the lower bound for an algorithm (or problemas explained lateris denoted by the symbol ohmpronounced "big-omegaor just "omega the following definition for ohm is symmetric with the definition of big-oh for (na non-negatively valued functiont(nis in set ohm( ( )if there exist two positive constants and such that ( >cg(nfor all an alternate (non-equivalentdefinition for ohm is (nis in the set ohm( ( )if there exists positive constant such that ( >cg(nfor an infinite number of values for this definition says that for an "interestingnumber of casesthe algorithm takes at least cg(ntime note that this definition is not symmetric with the definition of big-oh for (nto be lower boundthis definition does not require that ( >cg(nfor all values of greater than some constant it only requires that this happen often enoughin particular that it happen for an infinite number of values for motivation for this alternate definition can be found in the following example assume particular algorithm has the following behaviorn for all odd > (nn / for all even > for all even > sot( >cn for an infinite number from this definitionn / > of values of ( for all even nfor / thereforet(nis in ohm( by the definition