Which one of the following is the tightest upper bound that represents the…
2013
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) \)
Attempted by 756 students.
Show answer & explanation
Correct answer: B
Key idea: selection sort does at most one swap per outer iteration.
There are n-1 outer iterations (one for each position to fill), and each iteration performs at most one swap to place the chosen element.
Therefore the maximum number of swaps is n-1, which is O(n).
This bound is tight in the worst case (for example, when each iteration requires a swap), so O(n) is the tightest upper bound for the number of swaps.
A video solution is available for this question — log in and enroll to watch it.