How to determine the time complexity of the quicksort algorithm?

The time complexity of the QuickSort algorithm depends on the choice of the pivot element and the data distribution.

• In the average and best case, the complexity is O(n log n), where n is the number of elements. This occurs when the array is roughly divided in half at each step.
• In the worst case (for example, when the array is already sorted and the extreme element is chosen as the pivot), the complexity becomes O(n²).

To estimate the time complexity, the number of comparisons and swaps at each level of recursion are analyzed and summed across all levels.

Example of calling QuickSort in Java:

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Here, partition is a function that selects the pivot and divides the array.