if one assumes that each line of code takes one unit of time to executethe running time of this function can be described as the constant corresponds to the number of times the first loop is executed the term corresponds to the number of times the second loop is executed finallythe term corresponds to the time spent executing the two statements in the nested for loop consequentlythe call ( will print number of additions so far number of additions so far number of additions so far for small values of the constant term dominates if is of the steps are accounted for by the first loop on the other handif is each of the first two loops accounts for only of the steps when is , , the first loop takes about of the total time and the second loop about full , , , , of the , , , , steps are in the body of the inner for loop clearlywe can get meaningful notion of how long this code will take to run on very large inputs by considering only the inner loopi the quadratic component should we care about the fact that this loop takes steps rather than stepsif your computer executes roughly million steps per secondevaluating will take about hours if we could reduce the complexity to stepsit would take about hours in either casethe moral is the samewe should probably look for more efficient algorithm this kind of analysis leads us to use the following rules of thumb in describing the asymptotic complexity of an algorithmif the running time is the sum of multiple termskeep the one with the largest growth rateand drop the others if the remaining term is productdrop any constants the most commonly used asymptotic notation is called "big onotation big notation is used to give an upper bound on the asymptotic growth (often called the order of growthof function for examplethe formula (xo( means that the function grows no faster than the quadratic polynomial in an asymptotic sense welike many computer scientistswill often abuse big notation by making statements like"the complexity of (xis ( by this we mean that in the worst case will take ( steps to run the difference between function being "in ( )and "being ( )is subtle but important saying that (xo ( does not preclude the worst-case running time of from being considerably less that ( the phrase "big owas introduced in this context by the computer scientist donald knuth in the he chose the greek letter omicron because number theorists had used that letter since the late th century to denote related concept