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?
Answer: B. \(O(n) \) — 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…
- A.
\(O(log \ n) \) - B.
\(O(n) \) - C.
\(O(n \ log \ n)\) - D.
\(O(n^2) \)
Attempted by 959 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.
Explore the full course: Iocl Engineers Officers Grade A Paper 2