The difficulty of sorting bubbles

Question

I have seen in many places, the difficulty for sorting bubbles is O (n ² ).

But how can this be so, because the inner loop should always be executed ni 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; } } } 

Answer 1

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

So, it works in O(n*n/2) , which is considered O (n ² )

Answer 2

There are different types of time complexity: you use a large O notation, so all cases of this function will be at least complicated this time.

As you approach infinity, this may be basically the n ^ 2 temporary scenario of the worst case scenario. The complexity of time is not an exact art, but rather a rough estimate of what speed you can expect for this class of algorithm, and therefore you are trying to be too precise.

For example, the theoretical time complexity may well be n ^ 2, although theoretically it should be n * n-1 due to the fact that an unexpected overflow can be performed.

Answer 3

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

Answer 4

It O (n ^ 2), since length * length.