Какая сложность у подобного алгоритма?

Question

Правильно ли я понимаю, что:

for i in range(len(abc)):
    if i in zxc:

по сути имеет сложность O(n^2) так как мы имеем цикл сложностью O(n) и внутри него используем in, который так же имеет сложность O(n)?

Answer 1

Цикл for i in range(len(abc)) имеет сложность O(n), n - длина списка abc.

Операция if i in zxc, имеет сложность O(m), где m - длина списка zxc.

Общая сложность будет O(n * m).