Что такое N-Squared

N-Squared (N²) — это обозначение временной сложности алгоритма, где время выполнения растёт пропорционально квадрату размера входных данных.

Пример:

# O(n²) — вложенные циклы
def find_pairs(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])

Где встречается:

• Сортировка пузырьком (Bubble Sort)
• Проверка всех пар элементов
• Некоторые задачи динамического программирования

Проблема:
При больших n (например, 10⁶) такой алгоритм будет работать крайне медленно.

Оптимизация:
Замена на O(n log n) (например, сортировка слиянием) или хеш-таблицы (O(1) для поиска).