title: Subset algorithm between two lists -- why is the worst case when len(L1) = len(L2)?
body: <p>I have an algorithm that determines whether a list L1 is a subset of a list L2 (i.e. whether all elements in L1 are in L2):</p>
  
  <pre><code>def isSubset(L1, L2):
      for e1 in L1:
          matched = False
          for e2 in L2:
              if e1 == e2:
                  matched = True
                  break
          if not matched:
              return False
      return True
  </code></pre>
  
  <p>In the notes of my course, it says that "the worst case occurs when len(L1) = len(L2)", but why is this?</p>
  
  <p>My reasoning is: for a given L1 and L2, the worst case occurs when L1 is indeed a subset of L2 (in which case, for every L1, we have to go through every element in L2 to verify this).</p>
  
  <p>If this is the case (i.e. L1 is a subset of L2), then it's going to take longer to verify that L1 is a member of, say, [1,7,2,3,5,8,9,20], than it is to verify that it's a member of, say, [2,5,3].</p>
  
  <p>What is wrong with my reasoning?</p>