Why selection sort will require $O(N)$ time

Question

As per the example given in this MIT OCW link URL https://ocw.mit.edu/courses/civil-and-environmental-engineering/1-124j-foundations-of-software-engineering-fall-2000/lecture-notes/sorting/

Why selection sort requires $O(N)$ time since the number of exchanges is at most N. Pls give example algorithm that prove this fact. Below is excerpt taken from same MIT OCW URL for reference

Selection sort is easy to implement; there is little that can go wrong with it. However, the method requires $O(N^2)$ comparisons and so it should only be used on small files. There is an important exception to this rule. When sorting files with large records and small keys, the cost of exchanging records controls the running time. In such cases, selection sort requires $O(N)$ time since the number of exchanges is at most $N$.

Answer 1

It is simpler and more correct to say: selection sort requires $O(n)$ exchanges (and this is optimal in the worst case).

That doesn't imply $O(n)$ time, unless the other operations take negligible time. But from a theoretical standpoint, $O(n^2)$ is never negligible compared to $O(n)$.

In practice if a comparisons and related overhead takes $s$ seconds and an exchange and related overhead takes $e$ seconds, the total time will be

$$\frac{sn^2}2+cn=\left(\frac{sn}2+c\right)n.$$

This can be considered a linear behavior as long as $sn\ll c$. That could be true if the records are stored on a slow disk while the keys are cached in RAM.

---

This course plays a dangerous game with the Big-$O$ notation.

Answer 2

Suppose that the cost for comparing two keys is $A$ and that the cost for exchanging two records is $B$. Then the running time of selection sort is $$ O(An^2 + Bn). $$ If $A$ is much smaller than $B$ (by a factor of $\Omega(n)$), then the second term is dominant.