def issubset( )"""assumes and are lists returns true if each element in is also in and false otherwise ""for in matched false for in if = matched true break if not matchedreturn false return true figure implementation of subset test each time the inner loop is reached it is executed (len( times the function will execute the outer loop (len( )timesso the inner loop will be reached (len( )times thereforethe complexity of issubset is (len( )*len( )now consider the function intersect in figure def intersect( )"""assumesl and are lists returns list that is the intersection of and ""#build list containing common elements tmp [for in for in if = tmp append( #build list without duplicates result [for in tmpif not in resultresult append(ereturn result figure implementation of list intersection the running time for the part building the list that might contain duplicates is clearly (len( )*len( )at first glanceit appears that the part of the code that builds the duplicate-free list is linear in the length of tmpbut it is not the test not in result potentially involves looking at each element in resultand is therefore (len(result))consequently the second part of the implementation is (len(tmp)*len(result)since the lengths of result and tmp are bounded by the length of the smaller of and and since we ignore additive termsthe complexity of intersect is (len( )*len( )exponential complexity as we will see later in this bookmany important problems are inherently exponentiali solving them completely can require time that is exponential in the size of the input this is unfortunatesince it rarely pays to write program that has reasonably high probability of taking exponential time to run