Explanation of best case of Bubble Sort being O(n) and not O(n^2)?

Question

Given a Bubble Sort algorithm

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

In the case that the array given is already sorted, the if statement in the inner-loop will always be false breaking the inner for loop and incrementing j until A.length-i-1 is reached. When A.length-i-1 is reached, i is incremented. This process cycles until i reaches A.length-1.

My confusion:

If both nested loops iterate to their respective upper-bounds, although there are no swaps being made, wouldn't the time complexity still be O(n^2) for best-case? Can anyone explain simply to me why it would be O(n)

Answer 1

Consider the following code:

int[] bubbleSort(int[] arrayToBeSorted){
        int n = arrayToBeSorted.length; // length of array
        int temp = 0; // to store value temporarily
        int flag =0; // to check if given array already sorted or not
        for (int i=0;i<n-1;i++){
            for (int j=0;j<n-i-1;j++){
                if(arrayToBeSorted[j] > arrayToBeSorted[j+1]){
                    flag = 1;
                    temp = arrayToBeSorted[j];
                    arrayToBeSorted[j] = arrayToBeSorted[j+1];
                    arrayToBeSorted[j+1] = temp;
                }
            }
            //checking if array is sorted already or not
            if (flag ==0){
                System.out.println("Already sorted so time complexity is only O(N)");
                break;
            }
        }
        return arrayToBeSorted;
    }

If you have an unsorted array in the above code, then the nested for loop will be executed until the given array is sorted completely. Thus it will take n*n -> O(n*n) time complexity.

But if you provide an already sorted array, you can see in the above code, when i=0, then the nested j loop will be executed n-i-1 times but the code inside if block won't be executing.

for (int j=0;j<n-i-1;j++){
                if(arrayToBeSorted[j] > arrayToBeSorted[j+1]){
                    flag = 1;
                    temp = arrayToBeSorted[j];
                    arrayToBeSorted[j] = arrayToBeSorted[j+1];
                    arrayToBeSorted[j+1] = temp;
                }
            }

This means your array is already sorted. so the flag will remains 0 as it is. Thus before going to the second increment i.e i=1,

your loop will stop so you save another n iteration. Thus, the loop executes only n times not n*n times.

This will break your loop for further execution if array is already sorted

     if (flag ==0){
                System.out.println("Already sorted so time complexity is only O(N)");
                break;
            }

Answer 2

If the program is as is, yes it will still take O(n^2) for the best-case scenario. But you can enhance this program.

During your first pass, you will see that no exchange has taken place. You can keep a flag which checks that if during a pass no exchange has taken place, you don't need to further passes.

In that case, you will only do one pass and time complexity will be O(n)

Sample Program (Could be better structured):

        boolean previousIterationSwap = false;
        final int[] A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        for (int i = 0; i < A.length - 1; i++) {
            // After the first iteration check if previous iteration had any
            // swap
            if (i > 0 && !previousIterationSwap) {
                break;
            }
            for (int j = 0; j < A.length - i - 1; j++) {
                if (A[j] > A[j + 1]) {
                    previousIterationSwap = true;
                    final int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                } else {
                    previousIterationSwap = false;
                }
            }
        }