1.4k views

Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort?

1. $O(\log n$)
2. $O(n$)
3. $O(n \log n$)
4. $O(n^{2}$)
edited | 1.4k views

In selection max you can do is $n$ swaps..selecting the smallest element from all the elements and replacing it correct position so $O(n)$
edited by
+22
(n-1) swaps to be precise
+1
I should have written it with big oh notation
0
okay :)
+1
Word swap is important!
0

But the time complexity of Selection Sort is O(n2).. There are two loops, one inside the other

0
The question asks only for the number of swaps.
0

Ok. Thanks Sir... The book from where I read has given wrong algorithm, saying it to be Selection Sort.. As per that algorithm, number of swaps are also O(n2).

+10
Then you should never open that book again
0
ha ha ha :-D

1
2