simplistic introduction to algorithmic complexity def squarerootbi(xepsilon)"""assumes and epsilon are positive floats epsilon returns such that * is within epsilon of ""low high max( xans (high low)/ while abs(ans** >epsilonif ans** xlow ans elsehigh ans ans (high low)/ return ans figure using bisection search to approximate square root we saw that exhaustive enumeration was so slow as to be impractical for many combinations of and epsilon for exampleevaluating squarerootexhaustive( requires roughly one billion iterations of the loop in contrastevaluating squarerootbi( takes roughly twenty iterations of slightly more complex while loop when the difference in the number of iterations is this largeit doesn' really matter how many instructions are in the loop the multiplicative constants are irrelevant asymptotic notation we use something called asymptotic notation to provide formal way to talk about the relationship between the running time of an algorithm and the size of its inputs the underlying motivation is that almost any algorithm is sufficiently efficient when run on small inputs what we typically need to worry about is the efficiency of the algorithm when run on very large inputs as proxy for "very large,asymptotic notation describes the complexity of an algorithm as the size of its inputs approaches infinity considerfor examplethe code def ( )"""assume is an int ""ans #loop that takes constant time for in range( )ans + print 'number of additions so far'ans #loop that takes time for in range( )ans + print 'number of additions so far'ans #nested loops take time ** for in range( )for in range( )ans + ans + print 'number of additions so far'ans return ans