one of the interesting and sometimes even surprising aspects of the analysis of data structures and algorithms is the ubiquitous presence of the logarithm functionf(nlog nfor some constant this function is defined as followsx log if and only if bx by definitionlog the value is known as the base of the logarithm computing the logarithm function exactly for any integer involves the use of calculusbut we can use an approximation that is good enough for our purposes without calculus in particularwe can easily compute the smallest integer greater than or equal to log nfor this number is equal to the number of times we can divide by until we get number less than or equal to for examplethis evaluation of log is since / likewisethis evaluation of log is since / / and this approximation to log is since / / < this base-two approximation arises in algorithm analysisactuallysince common operation in many algorithms is to repeatedly divide an input in half indeedsince computers store integers in binarythe most common base for the logarithm function in computer science is in factthis base is so common that we will typically leave it off when it is that isfor uslogn log we note that most handheld calculators have button marked logbut this is typically for calculating the logarithm base- not base-two there are some important rules for logarithmssimilar to the exponent rules proposition (logarithm rules)given real numbers and we have log ac log log log / log alog log ac clog log (log )/log log log alsoas notational shorthandwe use logcn to denote the function (logn) rather than show how we could derive each of the identities above which all follow from the definition of logarithms and exponentslet us illustrate these identities with few examples instead