Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort? A. O(log n) B. O(n) C. O(n log n) D. O(n^2)

GATE 2013 · Algorithms · Sorting · easy

Answer: O(n) — selection sort requires at most n-1 swaps

1. Count maximum swaps: Each of the n-1 passes does exactly one swap in the worst case (when the minimum is never already in place). Maximum swaps = n-1.
2. Identify tightest upper bound: n-1 swaps = O(n). Among the options A=O(log n), B=O(n), C=O(n log n), D=O(n^2): O(log n) is too small, O(n) correctly upper-bounds n-1, and O(n log n)/O(n^2) are valid but looser. Tightest is O(n).