the algorithm on large numbers of items if an algorithm is such that we may consider all steps equally costlythen usually the complexity class of the algorithm is simply determined by the number of loops and how often the content of those loops are being executed the reason for this is that adding constant number of instructions which does not change with the size of the problem has no significant effect on the overall complexity for large problems there is standard notationcalled the big- notationfor expressing the fact that constant factors and other insignificant details are being ignored for examplewe saw that the procedure last(lon list had time complexity that depended linearly on the size of the listso we would say that the time complexity of that algorithm is (nsimilarlylinear search is (nfor binary searchhoweverthe time complexity is (log nbefore we define complexity classes in more formal mannerit is worth trying to gain some intuition about what they actually mean for this purposeit is useful to choose one function as representative of each of the classes we wish to consider recall that we are considering functions which map natural numbers (the size of the problemto the set of nonnegative real numbers rso the classes will correspond to common mathematical functions such as powers and logarithms we shall consider later to what degree representative can be considered 'typicalfor its class the most common complexity classes (in increasing orderare the followingo( )pronounced 'oh of one'or constant complexityo(log log )'oh of log log en' (log )'oh of log en'or logarithmic complexityo( )'oh of en'or linear complexityo(nlog )'oh of en log en' ( )'oh of en squared'or quadratic complexityo( )'oh of en cubed'or cubic complexityo( )'oh of two to the en'or exponential complexity as representativewe choose the function which gives the class its name for (nwe choose the function (nnfor (log nwe choose (nlog nand so on so assume we have algorithms with these functions describing their complexity the following table lists how many operations it will take them to deal with problem of given sizef ( log log log nlog =