def inttostr( )"""assumes is nonnegative int returns decimal string representation of ""digits ' if = return ' result 'while result digits[ % result // return result since there are no function or method calls in this codewe know that we only have to look at the loops to determine the complexity class there is only one loopso the only thing that we need to do is characterize the number of iterations that boils down to the number of times one can divide by sothe complexity of inttostr is (log( )what about the complexity of def adddigits( )"""assumes is nonnegative int returns the sum of the digits in ""stringrep inttostr(nval for in stringrepval +int(creturn val the complexity of converting to string is (log( )and inttostr returns string of length (log( )the for loop will be executed (len(stringrep)timesi (log( )times putting it all togetherand assuming that character representing digit can be converted to an integer in constant timethe program will run in time proportional to (log( ) (log( ))which makes it (log( )linear complexity many algorithms that deal with lists or other kinds of sequences are linear because they touch each element of the sequence constant (greater than number of times considerfor exampledef adddigits( )"""assumes is str each character of which is decimal digit returns an int that is the sum of the digits in ""val for in sval +int(creturn val this function is linear in the length of si (len( ))--again assuming that character representing digit can be converted to an integer in constant time of coursea program does not need to have loop to have linear complexity