logarithm rules from proposition (using the usual convention that the base of logarithm is if it is omittedlog( nlog log lognby rule log( / logn log logn by rule logn lognby rule log nlog = nby rule log (log )log (logn/ by rule logn nlog nby rule as practical matterwe note that rule gives us way to compute the base-two logarithm on calculator that has base- logarithm buttonlogfor log logn/log the linear function another simple yet important function is the linear functionf( ) that isgiven an input value nthe linear function assigns the value itself this function arises in algorithm analysis any time we have to do single basic operation for each of elements for examplecomparing number to each element of an array of size will require comparisons the linear function also represents the best running time we can hope to achieve for any algorithm that processes collection of objects that are not already in the computer' memorysince reading in the objects itself requires operations the -log- function the next function we discuss in this section is the -log- functionf(nnlognthat isthe function that assigns to an input the value of times the logarithm base-two of this function grows little faster than the linear function and lot slower than the quadratic function thusas we will show on several occasionsif we can improve the running time of solving some problem from quadratic to -lognwe will have an algorithm that runs much faster in general