computational complexity asymptotic lower bound ( ( ) (nc and omega notation serves as way to describe lower bound of function in this case the lower bound definition says for while it might be greaterbut eventually there is some where (ndominates (nfor all bigger values of in that casewe can write that the algorithm is ( ( )considering our graph once againwe see that the purple line is dominated by the observed behavior sometime after as with the upper boundfor while the lower bound may be greater than the observed behaviorbut after whilethe lower bound stays below the observed behavior for all bigger values of with both lower bound and and upper bound definitionwe now have the notation to define an asymptotically tight bound this is called theta notation theta asymptotic tight bound ( ( ) (nc and if we can find such function gthen we can declare that ( ( )is an asymptotically tight bound for ( )the observed behavior of an algorithm in fig the upper bound blue line is (nn and the lower bound purple line is plot of ( )/ if we let and / we have the asymptotically tight bound of (nat ( nowinstead of saying that -squared is an upper bound on the algorithm' behaviorwe can proclaim that the algorithm truly runs in time proportional to -squared the behavior is bounded above and below by functions of -squared proving the claim that the algorithm is an -squared algorithm amortized complexity sometimes it is not possible to find tight upper bound on an algorithm for instancemost operations may be bounded by some function * (nbut every once in while there may be an operation that takes longer in these cases it may be helpful to employ something called amortized complexity amortization is term used by accountants when spreading the cost of some business transaction over number of years rather than applying the whole expense to the books in one fiscal year this same idea is employed in computer science when the cost of an operation is averaged the key idea behind all amortization methods is to get as tight an upper bound as we can for the worst case running time of any sequence of operations on data structure (which usually starts out emptyby dividing by we get the average or amortized running time of each operation in the sequence this copy belongs to 'acha