simplistic introduction to algorithmic complexity when we say that (xis ( )we are implying that is both an upper and lower bound on the asymptotic worst-case running time this is called tight bound some important complexity classes some of the most common instances of big are listed below in each casen is measure of the size of the inputs to the function ( denotes constant running time (log ndenotes logarithmic running time (ndenotes linear running time ( log ndenotes log-linear running time (nkdenotes polynomial running time notice that is constant (cndenotes exponential running time here constant is being raised to power based on the size of the input constant complexity this indicates that the asymptotic complexity is independent of the inputs there are very few interesting programs in this classbut all programs have pieces (for example finding out the length of python list or multiplying two floating point numbersthat fit into this class constant running time does not imply that there are no loops or recursive calls in the codebut it does imply that the number of iterations or recursive calls is independent of the size of the inputs logarithmic complexity such functions have complexity that grows as the log of at least one of the inputs binary searchfor exampleis logarithmic in the length of the list being searched (we will look at binary search and analyze its complexity in the next by the waywe don' care about the base of the logsince the difference between using one base and another is merely constant multiplicative factor for exampleo(log ( ) (log ( )*log ( )there are lots of interesting functions with logarithmic complexity consider the more pedantic members of the computer science community use big thetathrather than big for this