1.1k 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.1k 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
(n-1) swaps to be precise
I should have written it with big oh notation
okay :)
Word swap is important!

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

The question asks only for the number of swaps.

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).

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