characterizing running times using the big-oh notation the big-oh notation is used widely to characterize running times and space bounds in terms of some parameter nwhich varies from problem to problembut is always defined as chosen measure of the "sizeof the problem for exampleif we are interested in finding the largest element in sequenceas with the find max algorithmwe should let denote the number of elements in that collection using the big-oh notationwe can write the following mathematically precise statement on the running time of algorithm find max (code fragment for any computer proposition the algorithmfind maxfor computing the maximum element of list of numbersruns in (ntime justificationthe initialization before the loop begins requires only constant number of primitive operations each iteration of the loop also requires only constant number of primitive operationsand the loop executes times thereforewe account for the number of primitive operations being for appropriate constants and that reflectrespectivelythe work performed during initialization and the loop body because each primitive operation runs in constant timewe have that the running time of algorithm find max on an input of size is at most constant times nthat iswe conclude that the running time of algorithm find max is (nsome properties of the big-oh notation the big-oh notation allows us to ignore constant factors and lower-order terms and focus on the main components of function that affect its growth example is ( justificationnote that <( ) cn for when > in factwe can characterize the growth rate of any polynomial function proposition if (nis polynomial of degree that isf (na ad nd and ad then (nis (nd justificationnote thatfor > we have < < <<nd hencea ad nd <(| | | |ad |nd we show that (nis (nd by defining | | |ad and