algorithm analysis the idea of these definitions is to establish relative order among functions given two functionsthere are usually points where one function is smaller than the other so it does not make sense to claimfor instancef(ng(nthuswe compare their relative rates of growth when we apply this to the analysis of algorithmswe shall see why this is the important measure although , is larger than for small values of nn grows at faster rateand thus will eventually be the larger function the turning point is , in this case the first definition says that eventually there is some point past which (nis always at least as large as ( )so that if constant factors are ignoredf(nis at least as big as (nin our casewe have ( , nf(nn , and we could also use and thuswe can say that , ( (order -squaredthis notation is known as big-oh notation frequentlyinstead of saying "order ,one says "big-oh if we use the traditional inequality operators to compare growth ratesthen the first definition says that the growth rate of (nis less than or equal to (<=that of (nthe second definitiont( ( ( )(pronounced "omega")says that the growth rate of (nis greater than or equal to (>=that of (nthe third definitiont( ( ( )(pronounced "theta")says that the growth rate of (nequals (=the growth rate of (nthe last definitiont(no( ( )(pronounced "little-oh")says that the growth rate of (nis less than (<the growth rate of (nthis is different from big-ohbecause big-oh allows the possibility that the growth rates are the same to prove that some function (no( ( ))we usually do not apply these definitions formally but instead use repertoire of known results in generalthis means that proof (or determination that the assumption is incorrectis very simple calculation and should not involve calculusexcept in extraordinary circumstances (not likely to occur in an algorithm analysiswhen we say that (no( ( ))we are guaranteeing that the function (ngrows at rate no faster than ( )thus (nis an upper bound on (nsince this implies that ( ( ( ))we say that (nis lower bound on (nas an examplen grows faster than so we can say that ( or ( (nn and ( grow at the same rateso both (no( ( )and ( ( ( )are true when two functions grow at the same ratethen the decision of whether or not to signify this with (can depend on the particular context intuitivelyif ( then (no( ) (no( )and (no( are all technically correctbut the last option is the best answer writing ( ( says not only that (no( but also that the result is as good (tightas possible here are the important things to knowrule if (no( ( )and (no( ( ))then (at (nt (no( (ng( )(intuitively and less formally it is (max( ( ) ( ))))(bt (nt (no( (ng( )rule if (nis polynomial of degree kthen ( (nk