Selection Sort Algorithm in DSA Go - Time & Space Complexity

Time Complexity: Selection Sort Algorithm

O(n²)

Understanding Time Complexity

We want to understand how the time taken by Selection Sort changes as the list size grows.

How many steps does it take to sort a list of numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIndex := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

This code sorts an array by repeatedly finding the smallest remaining element and swapping it to the front.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop that scans the unsorted part to find the minimum element.
• How many times: The outer loop runs n-1 times, and for each, the inner loop runs fewer times, roughly n-i-1 times.

How Execution Grows With Input

As the list grows, the number of comparisons grows much faster because each new element requires scanning the rest.

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 list size, the work roughly quadruples.

Common Mistake

[X] Wrong: "Selection Sort is fast because it only swaps once per outer loop."

[OK] Correct: While swaps are fewer, the many comparisons inside the inner loop still take a lot of time, dominating the cost.

Interview Connect

Understanding Selection Sort's time complexity helps you compare it with faster sorting methods and shows your grasp of algorithm efficiency.

Self-Check

"What if we changed the inner loop to stop early when the list is already sorted? How would the time complexity change?"