How to determine the time complexity of a sorting algorithm?

The time complexity of an array sorting algorithm depends on the number of operations performed depending on the input size (usually denoted as n — the number of elements in the array).

To determine the time complexity, analyze how many times the main operations (e.g., comparisons and swaps) are performed in the worst, average, and best cases.

Express this number of operations as a function of n.

For example, bubble sort compares pairs of elements in nested loops, resulting in approximately n² operations, so the time complexity is O(n²).

Example: sorting an array with bubble sort and estimating complexity:

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Here, two nested loops over n, so the time complexity is O(n²).

For more efficient algorithms, such as quicksort, the average time complexity is O(n log n).