Quick Sort Algorithm in DSA C++ - Time & Space Complexity

Time Complexity: Quick Sort Algorithm

O(n log n)

Understanding Time Complexity

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

How does the number of steps grow when the input size increases?

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; j++) {
    if (arr[j] <= pivot) {
      i++;
      std::swap(arr[i], arr[j]);
    }
  }
  std::swap(arr[i + 1], arr[high]);
  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

• Primary operation: The for-loop inside partition that compares and swaps elements.
• How many times: This loop runs once for each element in the current sub-array during each recursive call.
• Recursion: The function calls itself twice on smaller parts after partitioning.
• Dominant operation: The repeated partitioning and recursive calls dominate the time.

How Execution Grows With Input

When the list is split evenly, the number of operations grows a bit more than the size of the list times the number of splits.

Input Size (n)	Approx. Operations
10	About 30 to 40 comparisons and swaps
100	About 700 to 800 comparisons and swaps
1000	About 10,000 to 12,000 comparisons and swaps

Pattern observation: The operations grow roughly like n times log n when splits are balanced.

Final Time Complexity

Time Complexity: O(n log n)

This means that as the list size doubles, the work grows a bit more than double, but much less than square.

Common Mistake

[X] Wrong: "Quick Sort always runs in linear time because it just splits the list."

[OK] Correct: Splitting takes time, and the partition step compares many elements. Also, if splits are uneven, it can take longer.

Interview Connect

Understanding Quick Sort's time complexity helps you explain why it is fast on average and what can slow it down, a key skill in interviews.

Self-Check

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