Почему Big O of Bubble рода Quadradic, если последнее взаимодействие прекращено?

Question

У меня есть следующий алгоритм Bubble sort:

    public void BubbleSort(int[] arr, int start, int end)
    {
        int instructions = 0;
        bool swapped = true;

        while (swapped)
        {
            swapped = false;
            for (int i = 0; i < arr.Length - 1; i++)
            {
                //instructions++;
                for (int j = i + 1; j < arr.Length; j++)
                {
                    instructions++;
                    if (arr[i] > arr[j])
                    {
                        int temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;

                        swapped = true;
                    }
                }
            }
        }

        Console.WriteLine("instructions++ " + instructions);
    }

если вы напечатаете instructions, вы увидите, что это точно: (n ^ 2) - n

Так почему же мыигнорировать -n?

Считается ли оно постоянным, хотя оно и зависит от размера ввода (было бы странно покупать эй ..)?

Answer 1

Время ловкости работает как таковое.Для больших значений n в этом случае линейный n не имеет значения.Например, если мы говорим о 10 миллионах чисел, значение (10 ^ 6) ^ 2 намного больше, чем 10 ^ 6.Таким образом, хотя он и существует, другой фактор затмевает его для больших n, поэтому его легче игнорировать.