Subconjunto algoritmo entre duas listas - por que é o pior caso quando len (L1) = len (L2)? - python, complexidade assintótica

Eu tenho um algoritmo que determina se uma lista L1 é um subconjunto de uma lista L2 (ou seja, se todos os elementos em L1 estão em L2):

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

Nas notas do meu curso, diz que "o pior caso ocorre quando len (L1) = len (L2)", mas por que isso acontece?

Meu raciocínio é: para um determinado L1 e L2, o pior caso ocorre quando L1 é de fato um subconjunto de L2 (nesse caso, para cada L1, temos que passar por todos os elementos em L2 para verificar isso).

Se este é o caso (ou seja, L1 é um subconjunto de L2), então vai demorar mais tempo para verificar que L1 é um membro de, digamos, [1,7,2,3,5,8,9,20 ], do que é para verificar que é um membro de, digamos, [2,5,3].

O que há de errado com meu raciocínio?

Respostas:

Basicamente, quando L1 é igual a L2, todos os elementos de L1 tem que ser verificado contra L2.

Por outro lado, se L1 não é igual a L2, ou é um subconjunto dele, ou não é.

Se for, menos verificações serão necessárias, uma vez que haverá menos elementos L1 do que se L1 foi contanto que L2.

Mais, assim que um elemento não pertencente a L2 é descoberto em L1, é certo que L1 não pode ser um subconjunto de L2.

Por outro lado, se len(L1) == len(L2) mas o primeiro elemento de L1 não está em L2, a execução exigirá apenas um loop L2.

Portanto, o pior caso => len(L1) == len(L2), mas o inverso não é verdade.