Quick Sort Algorithm in DSA Javascript - 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.

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}
    

This code sorts an array by picking a pivot, splitting the array into smaller parts, and sorting those parts recursively.

Identify Repeating Operations

• Primary operation: The for-loop that compares each element to the pivot to split the array.
• How many times: This loop runs once for each element in the current array segment, repeated recursively on smaller parts.
• Recursion: The function calls itself twice on smaller arrays (left and right), repeating the splitting and sorting.

How Execution Grows With Input

When the array size doubles, the number of comparisons grows roughly by a bit more than double because of the recursive splitting.

Input Size (n)	Approx. Operations
10	About 30 comparisons
100	About 700 comparisons
1000	About 10,000 comparisons

Pattern observation: The operations grow faster than the input size but slower than the square of the input size.

Final Time Complexity

Time Complexity: O(n log n)

This means that as the list gets bigger, the time to sort grows a little faster than the size but much slower than checking every pair.

Common Mistake

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

[OK] Correct: The time depends on how balanced the splits are; if the pivot is always the smallest or largest, it takes longer.

Interview Connect

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

Self-Check

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