Какая будет сложность, если перебирать цикл в цикле

Сложность вложенных циклов обычно O(n * m), где n и m — размеры внешнего и внутреннего циклов соответственно. Если оба цикла зависят от одного размера (например, оба до n), сложность становится O(n²).

Пример с квадратичной сложностью:

for i in range(n):        # O(n)
    for j in range(n):    # O(n)
        print(i, j)       # Итого: O(n²)

Нюансы:

• Если внутренний цикл зависит от внешнего (например, for j in range(i)), сложность остаётся O(n²), но с меньшим коэффициентом.
• Если внутренний цикл имеет фиксированный размер (например, 10 итераций), сложность становится O(n).
• Для тройного вложенного цикла с одинаковыми размерами — O(n³).

Важно анализировать реальное количество итераций, а не только уровень вложенности.