Какая временная сложность у пузырьковой сортировки

Временная сложность пузырьковой сортировки — O(n²) в худшем и среднем случае, и O(n) в лучшем случае (если массив уже отсортирован).

Почему O(n²):

• В худшем случае для каждого из n элементов делается n сравнений
• Даже с оптимизацией (флагом swapped) сложность остаётся квадратичной

Пример кода:

function bubbleSort(arr) {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
  } while (swapped);
  return arr;
}