Selection Sort Algorithm in DSA Javascript - Time & Space Complexity

Time Complexity: Selection Sort Algorithm

O(n²)

Understanding Time Complexity

We want to know how the time taken by selection sort changes as the list gets bigger.

How does the number of steps grow when sorting more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

This code sorts an array by repeatedly finding the smallest item and moving it to the front.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop compares elements to find the smallest item.
• How many times: The outer loop runs once for each element except the last, and the inner loop runs fewer times each pass but still many times overall.

How Execution Grows With Input

As the list grows, the number of comparisons grows much faster because each item is compared with many others.

Input Size (n)	Approx. Operations
10	About 45 comparisons
100	About 4,950 comparisons
1000	About 499,500 comparisons

Pattern observation: The operations grow roughly by the square of the input size.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the number of items, the work roughly quadruples.

Common Mistake

[X] Wrong: "Selection sort gets faster if the list is already sorted."

[OK] Correct: Selection sort always checks all pairs, so it takes the same time no matter the order.

Interview Connect

Understanding selection sort's time helps you compare it with faster methods and shows you can analyze simple algorithms clearly.

Self-Check

"What if we stopped searching for the minimum after finding the first smaller element? How would the time complexity change?"