CODEWITHSUNDEEP
javaalgorithmsortingtime-complexity
Deepak Kumar
Deepak Kumar

Reputation: 863

Complexity of Bubble Sort

I have seen at lot of places, the complexity for bubble sort is O(n2).

But how can that be so because the inner loop should always runs n-i times.

for (int i = 0; i < toSort.length -1; i++) {
            for (int j = 0; j < toSort.length - 1 - i; j++) {
                if(toSort[j] > toSort[j+1]){
                    int swap = toSort[j+1];
                    toSort[j + 1] = toSort[j];
                    toSort[j] = swap;
                }
            }
        }

Upvotes: 8

Views: 599

Answers (4)

Raquel Paz
Raquel Paz

Reputation: 1

It's O(n^2),because length * length.

Upvotes: 0

Nir Alfasi
Nir Alfasi

Reputation: 53525

And what is the "average" value of n-i ? n/2

So it runs in O(n*n/2) which is considered as O(n2)

Upvotes: 7

Liam Murphy
Liam Murphy

Reputation: 31

There are different types of time complexity - you are using big O notation so that means all cases of this function will be at least this time complexity.

As it approaches infinity this can be basically n^2 time complexity worst case scenario. Time complexity is not an exact art but more of a ballpark for what sort of speed you can expect for this class of algorithm and hence you are trying to be too exact.

For example the theoretical time complexity might very well be n^2 even though it should in theory be n*n-1 because of whatever unforeseen processing overhead might be performed.

Upvotes: 3

Akhilesh
Akhilesh

Reputation: 47

Since outer loop runs n times and for each iteration inner loop runs (n-i) times , the total number of operations can be calculated as n*(n-i) = O(n2).

Upvotes: 1

Related Questions