function name log log log constant logarithmic log-squared linear quadratic cubic exponential figure typical growth rates rule logk (nfor any constant this tells us that logarithms grow very slowly this information is sufficient to arrange most of the common functions by growth rate (see fig several points are in order firstit is very bad style to include constants or low-order terms inside big-oh do not say (no( or (no( nin both casesthe correct form is (no( this means that in any analysis that will require big-oh answerall sorts of shortcuts are possible lower-order terms can generally be ignoredand constants can be thrown away considerably less precision is required in these cases secondwe can always determine the relative growth rates of two functions (nand (nby computing limnf( )/ ( )using 'hopital' rule if necessary the limit can have four possible valuesr the limit is this means that (no( ( ) the limit is this means that ( ( ( ) the limit is this means that (no( ( ) the limit does not existthere is no relation (this will not happen in our contextusing this method almost always amounts to overkill usually the relation between (nand (ncan be derived by simple algebra for instanceif (nn log and (nn then to decide which of (nand (ngrows fasterone really needs to determine which of log and grows faster this is like determining which of log or grows faster this is simple problembecause it is already known that grows faster than any power of log thusg(ngrows faster than (none stylistic noteit is bad to say ( < ( ( ))because the inequality is implied by the definition it is wrong to write ( > ( ( ))because it does not make sense nf(nand limng(nthen limnf( )/ (nlimnf ( )/ ( )where (nand (nare the derivatives of (nand ( )respectively 'hopital' rule states that if lim