Why is bubble sort O(n^2)?

Question

for (int front = 1; front < intArray.length; front++)
{
    for (int i = 0; i  < intArray.length - front; i++)
    {
        if (intArray[i] > intArray[i + 1])
        {
            int temp = intArray[i];
            intArray[i] = intArray[i + 1];
            intArray[i + 1] = temp;
        }
    }
}

The inner loop is iterating: n + (n-1) + (n-2) + (n-3) + ... + 1 times.

The outer loop is iterating: n times.

So you get n * (the sum of the numbers 1 to n)

Isn't that n * ( n*(n+1)/2 ) = n * ( (n^2) + n/2 )

Which would be (n^3) + (n^2)/2 = O(n^3) ?

I am positive I am doing this wrong. Why isn't O(n^3)?

Solution 1

You are correct that the outer loop iterates n times and the inner loop iterates n times as well, but you are double-counting the work. If you count up the total work done by summing the work done across each iteration of the top-level loop you get that the first iteration does n work, the second n - 1, the third n - 2, etc., since the ith iteration of the top-level loop has the inner loop doing n - i work.

Alternatively, you could count up the work done by multiplying the amount of work done by the inner loop times the total number of times that loop runs. The inner loop does O(n) work on each iteration, and the outer loop runs for O(n) iterations, so the total work is O(n²).

You're making an error by trying to combine these two strategies. It's true that the outer loop does n work the first time, then n - 1, then n - 2, etc. However, you don't multiply this work by n to to get the total. That would count each iteration n times. Instead, you can just sum them together.

Hope this helps!

Solution 2

Your inner loop is iterating, IN TOTAL, as you said n + (n-1) + (n-2) + (n-3) + ... + 1 times. So it is O(n + (n-1) + (n-2) + (n-3) + ... + 1) = O(n(n+1)/2) = O(n^2)

Solution 3

The inner loop iterates n times(in worst case):

for(int i = front; i < intArray.length; i++)

The outer loop iterates n times:

for(int front = 0; front < intArray.length; front++)

Therefore O(n^2)

Solution 4

k=1(sigma k)n = n(n+1)/2
because:
  s = 1 +  2    + ... + (n-1) + n
  s = n + (n-1) + ... + 2     + 1
+)
===================================
  2s = n*(n+1)
   s = n(n+1)/2
in bubble sort, 
(n-1) + (n-2) + ... + 1 + 0 times compares 
which means, k=0(sigma k)n-1
, k=0(sigma k)n-1 equals [k=1(sigma k)n] - n
therefore, n(n+1)/2 - n = n(n-1)/2
which is 1/2(n^2-n) => O(1/2(n^2-n))
in big O notation, we remove constant, so
O(n^2-n)
n^2 is larger than n
O(n^2)

Solution 5

How you basically calculate N...

• Each line: +1

• Each Loop *N

  So you start adding numbers get to your first loop now you have N+1, you keep going and you eventually get N*N or N^2 for the time plus some number. Pulling off the number as it is generally insignificant compared to N.

Pretty much N is a representation of all the items in the loop kind of like 1,2,3...N. So it is simply representing a number not how many times a loop, loops.

View more solutions

Comments

[ordinary]

Ah just had the Aha moment. ty.

[Admin]

Might be worth adding that Big O describes the growth rate of an algorithm proportional to the size of the inputs which is not necessarily the same thing as the exact amount of iterations taken for the algorithm to run.

[ruralcoder]

Solve (n*(n+1))/2 for n=5 and you get 15, not 5^2=25. Not the same.

[Tiny]

Would it be accurate to say that BubbleSort completes (n-1)*(n-1) iterations? therefore N^2 iterations. This is the time complexity. Am I right in assuming this?

[Pankaj]

Bubblesort does not do (n-1)*(n-1), it does Outer loop (n-1) : inner loop [(n-1),(n-2),(n-3),...,(2),(1)] So you can say buble sort iterates for inner loop [(n-1),(n-2),(n-3),...,(2),(1)] times. Which is n(n-1)/2 times, which is not N^2 times, But as user "user849425" suggested in comment Above, Big O is not a number of iterations.

[Pankaj]

Big O notations are so confusing. Inner loop Does O(n-i) and NOT O(n)

[Aniket Kariya]

So can I write it as O((n*(n+1))/2) as well as O(n^2)?