Big Oh for while loop with empty body. For instance, used here in partition method of Quick Sort-CodePudding

Came across this implementation of partition method for quick sort, and was wondering what would be the Big Oh here, as it was using nested loops, although inner loop has empty body?

public static int partition(int[] arr, int start, int end) {
    int pivot = arr[start];
    int i = start;
    int j = end;

    while (i<j) {
        while (i<j && arr[--j] >= pivot) ;
        if (i<j) {
            arr[i] = arr[j];
        }

        while (i<j && arr[  i] <= pivot) ;
        if (i<j) {
            arr[j] = arr[i];
        }
    }
    arr[j] = pivot;
    return j;
}

CodePudding user response：

It's the standard basic Quick Sort. Empty body or not empty, it doesn't matter.

CodePudding user response：

An "empty" body of a loop does not equal "empty" code and "no work" being done. Here it is a while loop, but a for loop can also have an "empty" body.

So these are still loops, they just do all the work inside their condition part of the loop declaration.

This while loop

while (i<j && arr[--j] >= pivot);

still does some work. It does the i<j comparison and if it is true it does --j and uses the new decreased j value to compare arr[j] >= pivot and if this is also true it keeps going (repeats this all over again - note that j has a lower value after each iteration).

So in the worst case this is O(length of arr), when i is 0 (start) and --j is arr.length - 1 (end) and pivot is the smallest value in the array arr.

The function partition(int[] arr, int start, int end) is not only called at the start, but also again in recursive calls of the main quicksort(int[] arr, int start, int end) call. So start being 0 and end being at the end of the array arr only happens in the beginning, in recursive calls, start and end cover smaller and smaller parts of the array.

So in a general case it would be O(end - start) where end - start is <= arr.length.

Eventually start < end and thus i<j is not true anymore and then this loop is not even reached anymore, due to the i<j check that is done by the outer while loop. Only at that point (at those recursion levels) it does no work anymore.