the linear function another simple yet important function is the linear functionf (nn 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 sequence of size will require comparisons the linear function also represents the best running time we can hope to achieve for any algorithm that processes each of objects that are not already in the computer' memorybecause reading in the objects already requires operations the -log- function the next function we discuss in this section is the -log- functionf (nn log nthat isthe function that assigns to an input the value of times the logarithm base-two of this function grows little more rapidly than the linear function and lot less rapidly than the quadratic functionthereforewe would greatly prefer an algorithm with running time that is proportional to log nthan one with quadratic running time we will see several important algorithms that exhibit running time proportional to the -log- function for examplethe fastest possible algorithms for sorting arbitrary values require time proportional to log the quadratic function another function that appears often in algorithm analysis is the quadratic functionf (nn that isgiven an input value nthe function assigns the product of with itself (in other words" squared"the main reason why the quadratic function appears in the analysis of algorithms is that there are many algorithms that have nested loopswhere the inner loop performs linear number of operations and the outer loop is performed linear number of times thusin such casesthe algorithm performs operations