Você não está avaliando apropriadamente a performance. E sua explicação para ale · Silva97

Você não está avaliando apropriadamente a performance. E sua explicação para alegar que o segundo código é mais rápido não faz sentido, pois é literalmente necessário alterar o código para isso ser verdade. Levando em consideração o código que realmente está escrito no post, o segundo é pior em performance.

E se for para ter "licença poética" de modificar o código para dizer qual é mais rápido, então podemos modificar o primeiro para usar uma busca binária ao invés de busca linear. Logo é O(log n) (primeiro código) VS O(n) (segundo código), ou seja, o primeiro código é mais rápido.

E isso só levando em consideração o óbvio, mas podemos levar em consideração outros fatores também: O tipo list é implementado como dynamic array e o tipo set como hashtable. Considerando isto:

Dynamic array consome menos memória que hashtable.
Dynamic array é muito mais "cache friendly" do que hashtable, logo é mais perfomático para o processador.
Inserções em dynamic arrays sempre são O(1), mas inserções em hashtable são O((log n)^2) no pior caso.
Busca binária é O(log n) no pior caso e busca em hashtable é O((log n)^2) no pior caso.
A conversão de list para set causa alocação de memória implícita, que consome recursos a mais tanto de memória quanto de CPU comparado a simplesmente trabalhar com a list diretamente.
Já que o set() é alocado no escopo do if, então ele é alocado e imediatamente desalocado em seguida. Dando trabalho extra para o GC com uma estrutura que será usada em uma única operação.

Conclusão: Por vários motivos o primeiro código é mais performático que o segundo.

Ótima análise! De fato, se formos avaliar a implementação real do código no post, a conversão para set ali não faz sentido e acaba piorando a performance. A intenção era mostrar como a escolha da estrutura de dados pode impactar a eficiência, mas concordo que o exemplo não foi feliz e acabou gerando um efeito contrário.

Seu ponto sobre busca binária faz total sentido, e considerando a estrutura interna de list e set, há diversos fatores além da complexidade assintótica que influenciam no desempenho real, como consumo de memória, cache locality e até o comportamento do GC.

A lição que fica disso tudo é que otimização não é apenas sobre big-O, mas também sobre o comportamento real das estruturas e do hardware. Obrigado pelo comentário, sempre bom discutir esses detalhes!