Quick Sort as Divide and Conquer in DSA C - Time & Space Complexity

Time Complexity: Quick Sort as Divide and Conquer

O(n log n)

Understanding Time Complexity

We want to understand how the time to sort a list using Quick Sort changes as the list gets bigger.

Specifically, how many steps does Quick Sort take when sorting more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
        }
    }
    int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
    return i + 1;
}
    

This code sorts an array by picking a pivot, dividing the array around it, and sorting the parts recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The partition function loops through the array segment once to rearrange elements.
• How many times: The quickSort function calls itself twice on smaller parts, repeating partition on smaller segments until sorted.

How Execution Grows With Input

When the array size doubles, the number of operations grows more than double but less than square.

Input Size (n)	Approx. Operations
10	About 50 to 100 steps
100	About 700 to 1,000 steps
1000	About 10,000 to 15,000 steps

Pattern observation: The steps grow roughly proportional to n times log n, which is faster than simple repeated scanning but slower than quadratic.

Final Time Complexity

Time Complexity: O(n log n)

This means the sorting time grows a bit more than linearly but much less than checking every pair.

Common Mistake

[X] Wrong: "Quick Sort always takes the same time regardless of input order."

[OK] Correct: If the pivot choices are poor, Quick Sort can take much longer, even up to n squared steps.

Interview Connect

Understanding Quick Sort's time complexity helps you explain why it is fast on average and what can slow it down, showing your grasp of efficient algorithms.

Self-Check

"What if we always picked the middle element as pivot instead of the last? How would the time complexity change?"