Western Governors University (WGU) ICSC2100 C949 Data Structures and Algorithms I Practice Exam

Selection sort has a worst-case time complexity of O(n²) due to the algorithm's inherent structure and the way it processes the data. In selection sort, the array is divided into two parts: the sorted and the unsorted sections. The algorithm repeatedly selects the smallest (or largest, depending on sorting order) element from the unsorted section and swaps it with the first unsorted element, effectively growing the sorted section of the array.

For each of the n elements in the array, the algorithm scans the remaining unsorted elements to find the next smallest item. In the first iteration, it will make n comparisons, then (n - 1) in the second, and so on, down to 1 comparison in the final iteration. This results in a total of:

n + (n - 1) + (n - 2) + ... + 1 comparisons, which sums to n(n - 1)/2. This calculation simplifies to O(n²) in Big O notation, representing the dominant term for large n.

This quadratic time complexity means that as the size of the input increases, the time taken by selection sort increases significantly, which is why it is not efficient for large datasets compared to other sorting algorithms like quick