3 операции O(n) последовательно вложены, но все равно общий большой O равен O(n^2). Почему? ⇐ Python

[Anonymous]

Вопрос: «Оцените среднюю и наихудшую сложность, используя следующую запись: n = len(a)».

def anagramme_list(a, b): # Временная сложность: O(n^2) O(n^2) # Пространственная сложность: ~O(n) (список из строки) res = Ложь # O(1) O(1) if len(a) == len(b): # (cond O(1)) O(n^2) O(n^2) liste_b = список(b) # O(n) O(n) рез = Истина # O(1) O(1) for i in a: # (it: O(n)) O(n^2) O(n^2) если я в liste_b: # (cond O(n)) O(n) O(n) liste_b.remove(i) # O(n) O(n) иначе: # О(1) О(1) res = Ложь # O(1) O(1) вернуть разрешение Я бы сказал, что в худшем случае мы получим O(n^3), поскольку в O(n) есть операция (liste_b.remove(i)) инициируемая условием в O(n) (если я в списке_b), который сам вложен в цикл в O (n). Нет нужды говорить, что этот ответ меня удивил... Может ли кто-нибудь объяснить, почему вложенная операция в O (n) не считается «вложенной» в ее родителя («if i ​​in liste_b») и, на более широком уровне, как подойти к большой оценке O в этом тип корпуса, пожалуйста?