Quick Sort Partition Lomuto and Hoare in DSA Javascript - Time & Space Complexity

Time Complexity: Quick Sort Partition Lomuto and Hoare

O(n)

Understanding Time Complexity

We want to understand how the time taken by Quick Sort's partition steps changes as the input size grows.

Specifically, we look at Lomuto and Hoare partition methods to see how their operations scale.

Scenario Under Consideration

Analyze the time complexity of these two partition methods used in Quick Sort.

// Lomuto Partition
function lomutoPartition(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// Hoare Partition
function hoarePartition(arr, low, high) {
  let pivot = arr[low];
  let i = low - 1;
  let j = high + 1;
  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);
    if (i >= j) return j;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}
    

These functions rearrange elements around a pivot to help Quick Sort work efficiently.

Identify Repeating Operations

Both methods use loops to compare and swap elements around the pivot.

• Primary operation: Comparing elements to the pivot and swapping if needed.
• How many times: Each element between low and high is checked once in Lomuto; in Hoare, pointers move inward, each element visited at most once.

How Execution Grows With Input

As the number of elements (n) increases, the number of comparisons and swaps grows roughly in proportion to n.

Input Size (n)	Approx. Operations
10	About 10 comparisons and some swaps
100	About 100 comparisons and swaps
1000	About 1000 comparisons and swaps

Pattern observation: The operations increase linearly as input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the partition step takes time proportional to the number of elements it processes.

Common Mistake

[X] Wrong: "Partitioning is a constant time operation because it just picks a pivot."

[OK] Correct: Partitioning compares and swaps many elements, so its time grows with input size, not fixed.

Interview Connect

Understanding partition time helps you explain Quick Sort's efficiency clearly, a key skill in interviews.

Self-Check

"What if the pivot is always the smallest element? How would that affect the partition's time complexity?"