Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is bubble sort O(n^2)?

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)?

like image 930
ordinary Avatar asked Jul 13 '12 20:07

ordinary


People also ask

Why is space complexity of bubble sort O 1?

The space complexity for Bubble Sort is O(1), because only a single additional memory space is required i.e. for temp variable. Also, the best case time complexity will be O(n), it is when the list is already sorted.

Why does bubble sort Need 2 for loops?

The Bubble Sort algorithm utilizes two loops: an outer loop to iterate over each element in the input list, and an inner loop to iterate, compare and exchange a pair of values in the list. The inner loop takes (N-1) iterations while the outer loop takes N iterations.

Why does bubble sort need n 1 passes?

Since each pass places the next largest value in place, the total number of passes necessary will be n−1. After completing the n−1 passes, the smallest item must be in the correct position with no further processing required. ActiveCode 1 shows the complete bubbleSort function.

What is the complexity of bubble sort algorithm?

Summary. Bubble Sort is an easy-to-implement, stable sorting algorithm with a time complexity of O(n²) in the average and worst cases – and O(n) in the best case.


2 Answers

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(n2).

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!

like image 193
templatetypedef Avatar answered Nov 15 '22 19:11

templatetypedef


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)

like image 27
GL770 Avatar answered Nov 15 '22 21:11

GL770