sec asymptotic analysis example assume (nc for and thenc > for all sot( >cn for and thereforet(nis in ohm( by the definition it is also true that the equation of example is in ohm(nhoweveras with big-oh notationwe wish to get the "tightest(for ohm notationthe largestbound possible thuswe prefer to say that this running time is in ohm( recall the sequential search algorithm to find value within an array of integers in the average and worst cases this algorithm is in ohm( )because in both the average and worst cases we must examine at least cn values (where is / in the average case and in the worst caseth notation the definitions for big-oh and ohm give us ways to describe the upper bound for an algorithm (if we can find an equation for the maximum cost of particular class of inputs of size nand the lower bound for an algorithm (if we can find an equation for the minimum cost for particular class of inputs of size nwhen the upper and lower bounds are the same within constant factorwe indicate this by using th (big-thetanotation an algorithm is said to be th( ( )if it is in ( ( )and it is in ohm( ( )note that we drop the word "infor th notationbecause there is strict equality for two equations with the same th in other wordsif (nis th( ( ))then (nis th( ( )because the sequential search algorithm is both in (nand in ohm(nin the average casewe say it is th(nin the average case given an algebraic equation describing the time requirement for an algorithmthe upper and lower bounds always meet that is because in some sense we have perfect analysis for the algorithmembodied by the running-time equation for for this equation for ( )it is true that all inputs of size take at least cn time but an infinite number of inputs of size take cn timeso we would like to say that the algorithm is in ohm( unfortunatelyusing our first definition will yield lower bound of ohm(nbecause it is not possible to pick constants and such that ( >cn for all the alternative definition does result in lower bound of ohm( for this algorithmwhich seems to fit common sense more closely fortunatelyfew real algorithms or computer programs display the pathological behavior of this example our first definition for ohm generally yields the expected result as you can see from this discussionasymptotic bounds notation is not law of nature it is merely powerful modeling tool used to describe the behavior of algorithms